arXiv:2607.00427v1 [cs.SE] 1 Jul 2026
BT-APE: A Computationally Light Backtracking Approach to Automatic Prompt Engineering for Requirements Classification MOHAMMAD AMIN ZADENOORI, Department of Statistics, University of Padova, Italy WAAD ALHOSHAN, Imam Mohammad Ibn Saud Islamic University (IMSIU), Saudi Arabia JACEK DĄBROWSKI, Lero, the Research Ireland Centre for Software, University of Limerick, Ireland LIPING ZHAO, University of Manchester, United Kingdom ALESSIO FERRARI, University College Dublin (UCD), Ireland and Istituto di Scienza e Tecnologie dell’Informazione “A. Faedo” (ISTI), Consiglio Nazionale delle Ricerche (CNR), Italy Large language models (LLMs) are increasingly applied to requirements engineering (RE) tasks, including requirements classification, model generation, trace-link detection and others. Prompts, which guide LLM behavior, are typically designed manually through trial and error, often leading to inconsistent and suboptimal performance on RE tasks. Despite the importance of prompt design, prior RE research largely relies on manually constructed prompts and does not systematically optimize them; moreover, automated methods for prompt construction remain largely unexplored, leaving their effectiveness unclear. To address this gap, we propose a lightweight Automatic Prompt Engineering (APE) approach named Backtracking APE (BTAPE) and apply it to requirements classification as a representative RE task. We frame prompt design as an optimization problem and iteratively refine prompts using LLM-generated candidates, backtracking search, and dynamic example selection. We evaluate BT-APE on three benchmark datasets with five instruction-tuned LLMs against four classical prompting baselines (zero-shot, few-shot, chain-of-thought, and CoT+few-shot) and a state-of-the-art, yet more resource intensive, APE baseline (PE2). Our results show that BT-APE and PE2 achieve nearly identical performance, both substantially outperforming the four classical prompting baselines across datasets and models, with large effect sizes. However, compared with PE2, BT-APE imposes a substantially lighter computational footprint, consuming approximately 72% fewer cumulative input tokens and 66% less wall-clock time at equivalent accuracy (see Appendix C), making it better suited to deployment on small or resource-constrained servers. We also find that domain-informed prompt definitions enhance early performance, while iterative optimization partly compensates for weaker initial prompts. The contribution of this work is threefold: (i) a lightweight APE framework, together with an open interactive tool and replication package that operationalize the full pipeline; (ii) a comprehensive empirical evaluation across datasets and instruction-tuned LLMs that provides the first systematic comparison of APE against classical prompting for requirements classification; and (iii) insights into the impact of class definitions and prompt evolution on classification performance. CCS Concepts: • Computing methodologies → Natural language generation; • Software and its engineering → Software organization and properties. Authors’ Contact Information: Mohammad Amin Zadenoori, [email protected], Department of Statistics, University of Padova, Padova, , Italy; Waad Alhoshan, [email protected], Imam Mohammad Ibn Saud Islamic University (IMSIU), Riyadh, , Saudi Arabia; Jacek Dąbrowski, [email protected], Lero, the Research Ireland Centre for Software, University of Limerick, Limerick, Ireland; Liping Zhao, [email protected], University of Manchester, Manchester, , United Kingdom; Alessio Ferrari, [email protected], University College Dublin (UCD), Dublin, , Ireland and Istituto di Scienza e Tecnologie dell’Informazione “A. Faedo” (ISTI), Consiglio Nazionale delle Ricerche (CNR), Pisa, , Italy. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. © 2026 Copyright held by the owner/author(s). Publication rights licensed to ACM. ACM 1557-735X/2026/1-ART111 https://doi.org/XXXXXXX.XXXXXXX J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
111:2
Zadenoori et al.
Additional Key Words and Phrases: Large Language Models, LLMs, Natural Language Processing, NLP, Prompts Engineering, Automatic Prompting, Requirements Engineering, Requirements Classification ACM Reference Format: Mohammad Amin Zadenoori, Waad Alhoshan, Jacek Dąbrowski, Liping Zhao, and Alessio Ferrari. 2026. BTAPE: A Computationally Light Backtracking Approach to Automatic Prompt Engineering for Requirements Classification. J. ACM 00, 0, Article 111 (January 2026), 58 pages. https://doi.org/XXXXXXX.XXXXXXX
1
Introduction
Recent advances in Large Language Models (LLMs) are transforming Requirements Engineering (RE) [22, 57]. These models support tasks such as requirements elicitation, traceability, validation, and specification generation [32, 48]. Their effectiveness stems from large-scale pretraining and their ability to follow natural language instructions through in-context learning, without requiring task-specific training [57]. This capability is well suited to RE, where annotated data is often scarce, domain-specific, and costly to obtain, making traditional supervised approaches difficult to scale [58]. Interaction with LLMs is mediated through prompts, which are natural language instructions that guide model behavior and shape outputs [6]. Prompt quality directly affects performance, making prompt engineering a critical factor in LLM-based solutions [50]. However, in RE research, prompt design is typically manual and relies on iterative trial-and-error [57]. This process is often ad hoc and unsystematic, depends heavily on practitioner intuition, and is rarely documented in a reproducible manner [50]. As a result, it limits reproducibility and leads to inconsistent or suboptimal results across RE tasks and datasets [57]. Despite its importance, prompt engineering in RE remains underexplored [10, 23]. Existing studies rely on static prompting strategies—zero-shot, few-shot, and chain-of-thought—whose effectiveness is known to be highly sensitive to phrasing, ordering, and example selection [6]. Because these prompts are manually crafted and never updated in response to model behavior, they underutilized LLM capabilities. In contrast, recent work in the broader Natural Language Processing (NLP) literature introduces Automatic Prompt Engineering (APE) techniques that iteratively generate, evaluate, and refine prompts [24, 30, 51, 53]. These approaches frame prompt design as a search or optimization problem and have demonstrated strong performance improvements across a range of tasks [39]. However, their applicability to domain-specific RE problems, where terminology, structure, and ambiguity differ from general NLP benchmarks, remains unclear. Our prior short contribution introduced APE to RE and provided initial evidence that automated refinement can outperform standard prompting for requirements classification [55]. The preliminary study proposed a basic APE approach, focused on a single dataset and a single model, and did not analyze the effects of datasets, LLMs, or prompt design factors. This paper builds upon this study, by proposing a novel, more refined—yet lightweight—APE framework, named Backtracking-APE (BT-APE), and conducting a systematic empirical evaluation across multiple datasets and LLMs. The proposed BT-APE framework iteratively refines prompts using LLM-generated candidates, a backtracking search strategy, and dynamic example selection. We evaluate the effectiveness of the framework in RE and identify the factors that influence its performance. We focus on requirements classification as a representative RE task [9]. The task assigns labels to textual requirements, such as functional or non-functional categories. It supports downstream activities, including requirements analysis, prioritization, and quality assurance, it is the most frequently addressed task in NLP for RE research [58], and it has been shown to be highly relevant for industrial applications [2, 7]. The task also provides a controlled setting to assess the impact of prompt design on model behavior, given the availability of multiple benchmarks. We evaluate the approach on three benchmark datasets PROMISE [13], PROMISE-Refined [14], and SecReq [26] using five instruction-tuned LLMs in the J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
BT-APE: A Computationally Light Backtracking Approach to Automatic Prompt Engineering for Requirements Classification
111:3
7–8B parameter range: Qwen2-7B, Falcon3-7B, Granite-3.2-8B, Ministral-8B, and LLaMA-3-8B. We deliberately focus on instruction-tuned variants because BT-APE relies on the model’s ability to follow natural-language meta-prompts that ask it to revise an existing prompt conditioned on labelled feedback. We restrict the comparison to the 7–8B parameter range so that all models can be hosted locally on a single commodity GPU, reflecting the practical RE setting in which requirements confidentiality discourages reliance on hosted proprietary APIs. Furthermore, we analyse how prompt components, such as class definitions and examples, evolve during optimisation. Our results show that BT-APE outperforms standard prompting strategies, and reaches performance that are equivalent with another, more resource consuming, state-of-the-art baseline method, i.e., PE2 [53], also generalizing across datasets and models. We also show that domain-informed, carefully engineered prompts improve early performance, while iterative optimization compensates for weaker initial prompts, confirming the effectiveness of BT-APE especially in scenarios where expert-crafted prompts are unavailable or difficult to design. We also observe that effective prompts share a recognizable profile: they tend to be concise and action-oriented (higher verb count), structurally clear (more punctuation markers), and lexically focused, whereas length, lexical diversity, and syntactic complexity correlate negatively with performance. This paper makes three contributions: (1) The first systematic evaluation of APE on requirements classification, comparing two singletrajectory APE methods against four classical prompting strategies across three datasets and five LLMs. We show that APE transfers to RE with large effect sizes over classical prompting. (2) Evidence that two structurally different APE designs — PE2’s history-conditioned proposals and our BT-APE’s bounded-backtracking with balanced example batches — converge to statistically indistinguishable accuracy. We characterize the operational trade-offs (per-iteration context size, search behavior, hyperparameter interpretability) that differentiate them. (3) An analysis of prompt-feature evolution under BT-APE that identifies lexical, syntactic, and semantic correlates of high-performing prompts. In addition, we release a GUI-based interactive tool that operationalises the full BT-APE pipeline, enabling practitioners to apply and experiment with the method on their own requirements classification tasks without prior expertise in prompt engineering or LLM tooling (described in Appendix D). The tool, datasets, prompts, optimisation traces, and evaluation scripts are released as a publicly available replication package on Zenodo [54]. To support the reproducibility and extensibility of this study, additional materials are provided in the appendices. Appendix A presents a hyperparameter sensitivity analysis and convergence dynamics for the backtracking mechanism, characterizing the influence of patience thresholds and iteration horizons. Appendix B details the PE2 baseline implementation, highlighting its structural differences from our BT-APE method. Appendix C provides a comprehensive computational efficiency and token overhead comparison between BT-APE and PE2. Appendix D describes an interactive tool that operationalizes the full optimization pipeline. Appendix E outlines a preliminary analysis of potential data leakage using Jaccard similarity, showing that mean similarity between LLM-generated requirement continuations and ground-truth texts remains low (0.10–0.16) across all five models, with no statistically significant difference between PROMISE and SecReq. Relation to the preliminary version. This article substantially extends our REFSQ 2025 research preview [55], which introduced APE to requirements classification as a single-dataset, single-model proof of concept without statistical analysis. Beyond the contributions listed above, the present work (i) refines the original procedure into BT-APE by adding bounded backtracking with an explicit patience threshold, a balanced four-tuple dynamic example selection mechanism, and 3-run majority-voted evaluation; (ii) broadens the empirical scope from one dataset and one LLM J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
111:4
Zadenoori et al.
to three datasets and five instruction-tuned LLMs, and adds PE2 [53] as a state-of-the-art APE baseline; (iii) replaces descriptive evaluation with a full inferential design (Wilcoxon signed-rank tests, Friedman tests with power analysis, and a linear mixed-effects model with trajectory-level random intercepts); (iv) introduces two research questions absent from the preview — the analysis of prompt-feature evolution (RQ3) and the comparison of informed vs. uninformed class-definition initialisation (RQ4); and (v) releases an interactive GUI-based tool, a hyperparameter sensitivity analysis, a computational-efficiency comparison with PE2, and a data-leakage probe based on Jaccard similarity. The remainder of this paper is organized as follows. Section 2 introduces background and terminology. Section 3 presents the proposed approach. Section 4 describes the research design. Section 5 reports the results. Section 6 discusses the findings. Section 7 outlines threats to validity. Section 8 concludes the paper. 2 2.1
Background and Related Works Traditional and Pre-trained Machine Learning for Requirements Classification
Requirements classification, assigning predefined labels to natural language requirements, is a foundational RE task. Typical formulations distinguish functional from non-functional requirements, sort non-functional requirements into sub-types such as performance, security, and usability, and flag security-relevant requirements [13, 26, 29]. Automating this work matters because manual classification of large requirements documents is both impractical and error-prone. Early approaches leaned on traditional NLP and hand-crafted features—term frequency, bag-ofwords, and syntactic parsing—paired with classifiers such as support vector machines and Naïve Bayes [13, 29]. These pipelines demanded heavy preprocessing and domain-specific feature design, which limited their portability across datasets and domains [18, 58]. The arrival of transfer learning with pre-trained language models shifted the picture: Hey et al. [21] proposed NoRBERT, applying BERT-based transfer learning to achieve strong results on the PROMISE dataset across binary and multi-class tasks; Dalpiaz et al. [14] contributed refined PROMISE annotations and explored interpretable models using dependency-parsing features; and Alhoshan et al. [4] showed that pre-trained models can classify requirements with no task-specific training data, albeit with a measurable gap relative to supervised baselines. Addressing the natural variance and instability inherent to individual language architectures, Alsanoosy [5] unified these classic deep learning threads by implementing an ensemble learning framework across seven distinct models (including BERT and RoBERTa). 2.2
LLMs and In-Context Learning
Modern LLMs are transformer-based networks trained on large text corpora through self-supervised objectives, and models in the GPT family represent the current state of the art across classification, summarization, translation, and code generation, frequently without task-specific fine-tuning [3]. The property that most distinguishes these models from earlier neural approaches is in-context learning: given a natural language prompt containing instructions and, optionally, a handful of demonstrations, the model produces appropriate outputs without any parameter updates. This makes LLMs especially appealing for RE, where labeled datasets tend to be small and tightly bound to a particular domain [17]. Because state-of-the-art models contain hundreds of billions of parameters and are typically reached through hosted inference APIs rather than fine-tuned locally, the practical lever available to most RE researchers is no longer the model’s weights but the text of the prompt itself [23]. Within RE, LLMs have been applied well beyond classification—to elicitation, validation, traceability, and specification generation [17, 42, 43]. Ferrari et al. [17] explored generating UML J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
BT-APE: A Computationally Light Backtracking Approach to Automatic Prompt Engineering for Requirements Classification
111:5
sequence diagrams from requirements, while Rodriguez et al. [42] studied how prompt design shapes automated software traceability. Recently, SLMs are increasingly preferred over LLMs due to their efficiency and competitive performance on specialized tasks [32, 33]. Studies have shown that SLMs can match or even outperform LLMs in domain-specific applications such as requirements classification, while also significantly reducing computational and energy costs [15, 56]. 2.3
LLMs in Requirements Classification
Recent work on requirements classification has moved from traditional machine learning and encoder-based baselines toward LLM-based approaches. Santos et al. [43] report that few-shot and zero-shot prompting with GPT-4 and open-source models can approach the performance of fine-tuned transformers in some settings, indicating that both model choice and prompt design influence results. Peer et al. [37] propose NLP4ReF, which combines NLTK with ChatGPT and shows that classical toolkits remain effective for basic classification, while generative LLMs are useful for identifying missing or overlooked requirements during design reviews. Several studies address limitations of LLMs in this setting. To mitigate data sparsity and class imbalance in non-functional requirement (NFR) datasets, Qin and Peng [40] propose ChatNRC, a generative-discriminative framework that uses LLMs to synthesize application-specific NFRs. Shafikuzzaman et al. [44] compare prompting strategies and find that zero-shot configurations provide a label-free baseline, while few-shot prompting yields higher precision in multi-class NFR classification. To address the computational cost and limited interpretability of large models, Rejithkumar and Anish [41] introduce NICE, which distills reasoning chains from GPT-4o into smaller models such as T5 to support multi-label classification with natural language rationales validated by humans. 2.4
Prompt Engineering
Prompt engineering refers to the practice of designing and refining the natural language instructions supplied to an LLM in order to elicit a desired output. Because performance is highly sensitive to wording, structure, and the presence or absence of examples [42], prompting has come to be treated as a tunable interface for steering model behavior without retraining—sometimes characterized as a new programming paradigm [23]. The field organizes its techniques along two axes useful for our purposes. The first is the degree of supervision: zero-shot prompting supplies instructions alone, few-shot prompting adds a small set of input–output demonstrations, and chain-of-thought (CoT) prompting elicits intermediate reasoning before a final answer [52]. In RE classification settings, few-shot prompting has generally produced the strongest results [4, 42]. The second axis is the degree of automation. Early prompt engineering was a wholly manual, trial-and-error activity, but a line of work on automatic prompt optimization has since sought to reduce that effort by searching for effective prompts systematically. Zhou et al. [60] proposed APE, which casts prompt generation as black-box optimization—an LLM proposes candidate instructions, each is scored on a training set, and the best is selected—showing that machine-generated prompts can rival or exceed human-written ones. Building on this, Ye et al. [53] formalized prompt engineering as an optimization problem and proposed PE2, which iteratively refines prompts using LLM-generated feedback on misclassified examples, while Pryzant et al. [39] introduced ProTeGi, which performs a gradient-descent-like search in text space using natural language “gradients.” Other strands explore reinforcement-learning-based optimization [30], mixture-of-expert prompt construction [51], and evolutionary search [24]. Beyond supervision and automation, prompting also encompasses techniques such as retrieval-augmented generation [31], constraint injection, and multi-role dialogue, which broaden the surface available for adapting an LLM to a new domain [23]. J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
111:6
2.5
Zadenoori et al.
Prompt Engineering for Requirements Engineering
Taken together, these threads explain why prompting has become central to LLM-based RE, but they also expose a gap: the RE community still lacks a consolidated account of which prompting techniques map to which RE tasks, and with what trade-offs. General prompt-engineering taxonomies exist but tend to mix levels of abstraction—placing techniques, objectives, and application domains at the same hierarchical level—which makes them awkward to apply within RE [23]. The recent systematic review by Huang et al. [23] addresses this directly: following established secondarystudy [25] and mapping [38] guidelines, the authors screen several hundred records down to 35 primary studies and propose a hybrid taxonomy that links technique-oriented prompting patterns (e.g., few-shot, chain-of-thought, knowledge augmentation, self-reflection) to task-oriented RE roles (elicitation, validation, traceability, and others). Their analysis finds that contextualization and step-wise reasoning are the most widely adopted strategies—often used together—while multimodal prompting is essentially absent, requirements elicitation is under-explored, and systematic evaluation such as ablation studies is rare. They distill these gaps into a road-map toward reproducible, practitioner-ready PE4RE workflows. 2.6
Research Gaps and Contributions
Based on the literature review, there are gaps at the intersection of requirements classification, LLMs, and prompt engineering: • No APE for RE classification. While LLM-based approaches have shown promising results for requirements classification, existing studies rely exclusively on manually crafted prompting strategies—zero-shot, few-shot, or chain-of-thought—without systematically optimizing the prompt content itself [4, 42, 43]. Prompt design has been shown to significantly affect classification performance, yet the selection of prompts remains a largely ad-hoc process in the RE literature. • APE methods untested on domain-specific RE tasks. APE methods such as APE [60], PE2 [53], EPiC [46], and ProTeGi [39] have demonstrated strong results on general NLP benchmarks, but none have been applied or evaluated on domain-specific RE tasks. It remains unclear whether the gains observed on general benchmarks transfer to specialized classification problems such as requirements categorization. • Role of prompt phrasing unexplored. No prior work has investigated how the textual phrasing of category descriptions within the prompt influences the optimisation process. Understanding whether domain-grounded phrasings offer a lasting advantage over minimal ones, or whether iterative optimisation can compensate for weaker starting points, has both practical and theoretical implications. • Limited understanding of effective prompt characteristics. Existing studies treat prompts as fixed inputs and evaluate only the classification output, without analyzing how prompt characteristics—such as length, lexical diversity, syntactic complexity, or semantic specificity—relate to performance. There is no systematic understanding of what makes a prompt effective or how prompt properties evolve during iterative optimization. Our work addresses these gaps through the following contributions. We employ an APE approach for requirements classification that implements a backtracking-enhanced local search strategy to iteratively optimize prompts, going beyond the static prompt designs used in prior RE studies. We apply and evaluate this approach across multiple LLMs and three well-established requirements classification datasets, enabling a robust assessment of generalization. We introduce two initializations to isolate and quantify the effect of class definition quality on optimization performance. Finally, we conduct a feature-based analysis of prompt evolution across iterations, examining how J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
BT-APE: A Computationally Light Backtracking Approach to Automatic Prompt Engineering for Requirements Classification
111:7
lexical, syntactic, and semantic characteristics of prompts relate to classification performance. To the best of our knowledge, this is the first study to apply iterative APE adapted from the literature to requirements classification, and the first to systematically investigate the role of class definitions as a design variable in this particular process. 3 3.1
Approach BT-APE: Backtracking-Enabled APE Method overview
At a high level, BT-APE turns prompt design into a guided search. We start from an initial prompt that describes the classification task, and we let an LLM repeatedly propose revised versions of that prompt in light of how the current prompt is performing on labelled examples. The procedure proceeds in three phases. Initialisation sets up the search. We split the labelled data into three disjoint pools: one for sampling demonstration examples, one for scoring candidate prompts during the search, and one held out for a single final evaluation. We then score the initial prompt on the validation pool to establish a starting reference score against which all subsequent candidates will be compared. Iterative refinement is the core of the search. At each iteration, the LLM proposes a new candidate prompt conditioned on the current prompt and on a small, balanced batch of examples drawn from the example pool. The batch deliberately mixes successes and failures from both classes so that the proposer simultaneously sees where the current prompt works and where it breaks. Each candidate is scored on the validation pool and added to a ranked list. If the candidate improves on the best score seen so far, the search continues along this trajectory; if several consecutive candidates fail to improve, the search backtracks to a previously promising prompt rather than drifting further into an unproductive region of the prompt space. Held-out evaluation touches the third pool exactly once: the best prompt found during the search is scored on it to produce the final reported performance. Confining the search entirely to the validation pool and reserving the test pool for a single terminal evaluation prevents the selection pressure inherent in any search procedure from inflating the reported results. Three principles distinguish BT-APE from other single-trajectory APE methods such as PE2 [53]: (i) bounded backtracking, which abandons unproductive trajectories only after a configurable patience threshold rather than reactively at every non-improving step; (ii) balanced dynamic example selection, which guarantees the proposer always sees both classes and both success and failure signals; and (iii) conditioning the proposer on only the current prompt and a compact balanced batch, keeping the per-iteration context size bounded. We elaborate on these design choices and contrast them with PE2 in Section 3.4. 3.2
Formalisation
More formally, and building on the formulation by Ye et al. [53], prompt engineering can be cast as an optimisation problem: identify the optimal prompt 𝑝 ∗ that maximises a task-specific evaluation metric over a dataset 𝐷 = (𝑋, 𝑌 ), using an LLM M: 𝑝 ∗ = arg max 𝑓 M (𝑋, 𝑝), 𝑌 ,
(1)
𝑝
where • 𝐷 = (𝑋, 𝑌 ) is the dataset of input–output pairs (𝑥, 𝑦); • M takes a prompt 𝑝 and input 𝑥 ∈ 𝑋 to produce an output 𝑦 ′ ∈ 𝑌 ′ ; • 𝑓 is the evaluation function to be maximised (e.g., precision, recall, or F1 score). J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
111:8
Zadenoori et al.
Phase 1: Initialization
Phase 2: Iterative Refinement
30%
Dpool
Phase 3: Held-out Evaluation
Nmax = 20 iteration steps
E: 2 random positive + 2 random negative examples
1. Generate Candidate Prompt
Pool
Candidate Prompt pn
pcurr
APE generation conditioned on E 30%
Final Evaluation
2. Evaluate Candidate
Best Prompt
Validation
p*
Dval
DTest
LLM
F(pn) = Fval(pn), 3-run voting Ftest(p*)
DVal
Initial Prompt p1
3. Ranked List Update
4. Compare to Best YES Update p* and F* metric, reset c
F1* = FVal(p1)
Validation
Single 3-run evaluation
and advance ptr
… … …
Dataset D
F(pn) ≥ F1*?
…
c↑
…
Increment c counter
Ranked List R
40% (p , F *, 0) 1 1 …
Dtest
5. Backtracking Check
…
6. Dynamic Example Selection
…
Test
Ranked List R
c↑ c=X
Backtrack to next-best prompt at ptr in R
Update pcurr, decrement ptr, reset c
pcurr
Correctly classified positive
Classify Dpool with 3-run voting
Correctly classified negative
Mis classified positive
Mis classified negative
Fig. 1. Overview of the BT-APE workflow applied to requirements classification, alongside Algorithm 1. Steps are to be followed sequentially. The figure was generated with AI assistance and then reviewed, refined, and validated step by step by Author 1.
In the context of requirements classification, each 𝑥 is a textual requirement and each 𝑦 its manually annotated class (e.g., functional or quality). The evaluation function 𝑓 is applied to the entire output set M (𝑋, 𝑝), reflecting aggregate metrics such as F1 over the dataset. 3.3 Algorithm and workflow Figure 1 and Algorithm 1 present the same procedure as a diagram and as pseudocode, respectively. We describe the three phases below, with line numbers referring to Algorithm 1. • Phase 1: Initialisation (ll. 1–5). The dataset 𝐷 is partitioned into 𝐷 pool (30%), 𝐷 val (30%), and 𝐷 test (40%); these proportions balance the competing demands of in-context learning, low-variance validation scoring, and a low-variance final test estimate (see Appendix A). The example batch 𝐸 is seeded with two random positive and two random negative examples from 𝐷 pool . The initial prompt 𝑝 1 is scored on 𝐷 val to obtain its weighted F1, which we denote 𝐹 ∗ and use throughout the search as the best-so-far reference score against which subsequent candidates are compared. The triple (𝑝 1, 𝐹 ∗, 0) is then inserted into the ranked list R. • Phase 2: Iterative refinement (ll. 6–22). For up to 𝑁 max = 20 iterations, the procedure performs six steps: 2.1 Generate candidate (l. 8). A new prompt 𝑝𝑛 is generated by the LLM, conditioned on the current prompt 𝑝 curr and the balanced example batch 𝐸. Conditioning on 𝐸 exposes the proposer to concrete instances of where the current prompt succeeds and fails, following the error-conditioned refinement principle introduced by ProTeGi [39] and PE2 [53]. 2.2 Evaluate candidate (l. 10). 𝑝𝑛 is scored on 𝐷 val using 3-run majority voting (Section 3.6). Voting reduces run-to-run variability at the cost of three inference passes per candidate; this matters because the backtracking trigger below depends on F1 comparisons across iterations, and evaluation noise would otherwise propagate directly into search dynamics. J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
BT-APE: A Computationally Light Backtracking Approach to Automatic Prompt Engineering for Requirements Classification
111:9
2.3 Update ranked list (l. 12). The triple (𝑝𝑛 , 𝐹 (𝑝𝑛 ), 𝑛) is inserted into R, kept sorted by F1. Maintaining the full ranked history (rather than only the current best) is what enables the bounded backtracking step below. 2.4 Compare to best (ll. 13–17). If 𝐹 (𝑝𝑛 ) ≥ 𝐹 ∗ , the best prompt and reference score are updated, the failure counter 𝑐 is reset, and the pointer 𝑝𝑡𝑟 advances. Otherwise, 𝑐 is incremented. 2.5 Backtracking check (ll. 18–21). If 𝑐 reaches the patience threshold 𝑋 = 3, the search abandons the current trajectory and resumes from the next-best prompt in R via the pointer 𝑝𝑡𝑟 . The threshold 𝑋 is an interpretable exploration–exploitation knob: 𝑋 = 1 over-reacts to evaluation noise, while large values waste iterations on plateaus. We set 𝑋 = 3 based on the sensitivity analysis in Appendix A. 2.6 Select examples for the next iteration (ll. 22–23). 𝐷 pool is re-classified with 𝑝 curr , and 𝐸 is refreshed with one correctly classified positive, one correctly classified negative, one misclassified positive, and one misclassified negative. This balanced four-tuple guarantees that the proposer simultaneously sees success and failure signals on both classes — a property that matters because the optimisation objective is F1 on a potentially imbalanced label distribution. • Phase 3: Held-out evaluation (l. 24). The best prompt 𝑝 ∗ is scored once on 𝐷 test under the same 3-run majority-voting protocol. Because 𝐷 test is consulted only at this final step, the reported F1 is a genuine held-out estimate rather than a selection-inflated one. 3.4
BT-APE: Method Design and Inspirations
We propose BT-APE (Back-Tracking APE), a lightweight prompt optimisation procedure designed for settings where labelled data is scarce and each candidate evaluation is expensive. Given an initial prompt 𝑝 0 and a small pool 𝐷 pool of labelled examples, BT-APE iteratively proposes new prompts conditioned on the model’s behaviour on a balanced batch of correct and incorrect predictions, and maintains a ranked history R of all candidates evaluated so far. The full procedure is given in Algorithm 1 and summarised in Figure 1. In the following, we describe the main elements of the approach, and then we describe the figure and the algorithm in details. The approach consists of three defining components. Explicit, bounded back-tracking. BT-APE maintains a ranked list R of all evaluated candidates sorted by F1, together with a pointer 𝑝𝑡𝑟 that identifies the prompt currently being refined. The search remains on the current trajectory until 𝑋 = 3 consecutive iterations fail to improve over the best score 𝐹 ∗ , at which point 𝑝𝑡𝑟 jumps to the next-best prompt in R. This yields an interpretable patience parameter and prevents the search from lingering in unproductive neighbourhoods of the prompt space. Balanced, dynamic example selection. At every iteration, after classifying 𝐷 pool with the current prompt 𝑝 curr , BT-APE re-samples the example batch 𝐸 to contain one correctly classified positive, one correctly classified negative, one misclassified positive, and one misclassified negative example. This guarantees that the proposer simultaneously sees success and failure signals on both classes—a property that matters because our optimisation objective is F1 on a potentially imbalanced label distribution. Stable evaluation via majority voting. Every candidate is evaluated on the held-out validation split using 3-run majority voting. Because the back-tracking trigger depends on F1 comparisons across iterations, evaluation noise directly affects search dynamics; majority voting reduces LLM stochasticity at the cost of three times the inference budget per candidate. We use a fixed 30/30/40 J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
111:10
Zadenoori et al.
Algorithm 1: Backtracking-Enhanced Prompt engineering with Dynamic Example Selection Input: Dataset 𝐷, LLM M, initial prompt 𝑝 1 , max iters 𝑁 max = 20, backtrack threshold 𝑋 = 3 Output: Best prompt 𝑝 ∗ , held-out test F1 // Phase 1: Initialization Split 𝐷 into 𝐷 pool (30%), 𝐷 val (30%), and 𝐷 test (40%); 𝐸 ← 2 random positive + 2 random negative examples from 𝐷 pool ; 𝐹 ∗ ← 𝐹 val (𝑝 1 ) ; // score initial prompt on validation set 𝑝 ∗ ← 𝑝 1 , 𝑝 curr ← 𝑝 1 , 𝑐 ← 0, 𝑝𝑡𝑟 ← 1; Insert (𝑝 1, 𝐹 ∗, 0) into ranked list R; // Phase 2: Iterative Refinement (validation-driven) for 𝑛 = 1 to 𝑁 max do // Step 2.1: Generate Candidate Generate candidate 𝑝𝑛 via APE from 𝑝 curr conditioned on examples 𝐸; // Step 2.2: Evaluate Candidate on validation set 𝐹 (𝑝𝑛 ) ← 𝐹 val (𝑝𝑛 ) ; // 3-run majority voting on 𝐷 val // Step 2.3: Update Ranked List Insert (𝑝𝑛 , 𝐹 (𝑝𝑛 ), 𝑛) into R, kept sorted by F1; // Step 2.4: Compare to Best if 𝐹 (𝑝𝑛 ) ≥ 𝐹 ∗ then 𝑝 ∗ ← 𝑝𝑛 , 𝐹 ∗ ← 𝐹 (𝑝𝑛 ); 𝑝 curr ← 𝑝𝑛 , 𝑐 ← 0, 𝑝𝑡𝑟 ← 𝑝𝑡𝑟 + 1; else 𝑐 ← 𝑐 + 1; // Step 2.5: Backtracking Check if 𝑐 = 𝑋 then 𝑝 curr ← next-best prompt in R at position 𝑝𝑡𝑟 ; 𝑝𝑡𝑟 ← 𝑝𝑡𝑟 − 1, 𝑐 ← 0; // Step 2.6: Select Examples for Next Iteration Classify 𝐷 pool using 𝑝 curr (3-run voting); 𝐸 ← 1 correctly classified positive, 1 correctly classified negative, 1 misclassified positive, 1 misclassified negative from 𝐷 pool ; // Phase 3: Final held-out evaluation (test set touched once) return 𝑝 ∗ and 𝐹 test (𝑝 ∗ ) ; // single 3-run evaluation of 𝑝 ∗ on 𝐷 test pool/val/test split throughout the search so that F1 values entered into R are directly comparable across iterations. 3.4.1 Baseline and Positioning. To assess whether the simplicity of BT-APE comes at a cost, we compare it against PE2 [53] as a representative baseline. PE2 is a natural point of comparison: it shares the same single-trajectory, history-aware backbone, and formalises prompt optimisation as a sequence of meta-prompted proposals 𝑝 (𝑡 +1) = Mproposal 𝑝 (𝑡 ) , 𝐵; 𝑝 meta , (2) over a batch 𝐵 = {(𝑥, 𝑦, 𝑦 ′ )} of inputs, ground-truth labels, and current predictions, with a history of prior prompts from which back-tracking is possible by re-selecting the top-𝑛 candidates from 𝑃 (0) ∪𝑃 (1) ∪. . .∪𝑃 (𝑡 ) at every step [53]. We exclude population-based evolutionary approaches such J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
BT-APE: A Computationally Light Backtracking Approach to Automatic Prompt Engineering for Requirements Classification
111:11
as EPiC [46] from this comparison: they are well suited to code generation, where auto-generated unit tests validated via AST parsing make the fitness oracle cheap and large populations can be evaluated in parallel at low cost—a setting that does not match our binary-classification task, where each candidate evaluation requires three full classification runs over 𝐷 val . BT-APE and PE2 differ along three axes that map onto the three components above, and each axis has a concrete resource-consumption consequence which we quantify empirically in Appendix C. First, PE2 re-selects the top-𝑛 prompts from the full history at every step, whereas BT-APE commits to the current trajectory and triggers an explicit jump only when a fixed patience threshold is exceeded. Conditioning each proposal on the top-𝑛 history means that PE2’s per-iteration input context grows roughly linearly with the iteration count, while BT-APE’s remains bounded. Empirically, at 𝑁 max = 20, PE2 consumes approximately 72% more cumulative input tokens than BT-APE across all 15 (dataset, LLM) configurations (paired Wilcoxon, 𝑝 < 10−4 , large effect size; see Table 15). Second, PE2 conditions the proposer on an unconstrained error batch; BT-APE enforces a classand outcome-balanced batch at every iteration. The use of failure examples to drive prompt edits is also central to ProTeGi [39], which conditions a “textual gradient” prompt on model errors and then applies a second prompt to edit 𝑝 0 in the opposite semantic direction. BT-APE adopts this principle without the two-step gradient-then-edit decomposition, since a single proposal call conditioned on a balanced error batch is sufficient in our binary-classification setting and avoids doubling the LLM call cost per iteration. Third, BT-APE relies on 3-run majority voting on a fixed validation split, ensuring directly comparable F1 values across iterations—a property that bandit-style subsampling, as used in ProTeGi’s selection step [39], would not preserve. Taken together, these three design choices translate into a substantially lighter resource profile at equivalent accuracy: in addition to the input-token reduction noted above, BT-APE incurs approximately 60% lower mean proposer latency and 66% shorter total wall-clock time than PE2 across the full experimental grid (Appendix C). On a cost-normalised basis, BT-APE delivers each percentage point of 𝑤𝐹 1 at roughly 27% of PE2’s input-token cost and 34% of its wall-clock cost. This is the main practical motivation for the design: it enables deployment on resource-constrained or air-gapped servers, which are typically preferred in RE settings where requirements confidentiality discourages reliance on hosted APIs. The defaults 𝑋 = 3 and 𝑁 max = 20 are motivated by the sensitivity analysis in Appendix A, which shows that 𝑋 = 1 yields unstable trajectories while 𝑋 ∈ {3, 5} behave comparably on accuracy at increasing resource cost. 3.5
Prompt Structure and Class Definitions
A central component of the BT-APE classification prompt is the set of class definitions that instruct the LLM on how to distinguish between requirement categories. In the optimisation loop, the class definitions are the primary variable component of the prompt 𝑝, while the surrounding scaffolding (output-format instructions, task framing) remains fixed. We restrict optimisation to class definitions for two reasons. First, the output-format instructions are dictated by the evaluation pipeline: rewriting them risks producing responses the parser cannot decode, conflating prompt-quality variation with parsing failures. Second, prior work on prompt sensitivity in classification tasks [6, 42] identifies category descriptions as the primary lever through which prompts influence label decisions, while task framing contributes comparatively little once a minimally adequate version is in place. Confining the search to this component also keeps the prompt space small enough to be explored within the bounded iteration budget (𝑁 max = 20). J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
111:12
Zadenoori et al.
Two strategies are proposed for initializing these definitions, each serving as a different starting point 𝑝 1 for the optimization process: (1) Simple Definitions (BT-APE-Uninformed). Class definitions are one-sentence intuitive descriptions written by Author 1 without consulting RE literature or standards, reflecting a minimal-effort starting point. Examples: “Functional: what the system should do.”; “Quality: how well the system should do it.” ; “Security: protection against unauthorised access or harm.” The full set is given in Appendix F. (2) Literature-Based Definitions (BT-APE-Informed). Class definitions are curated and synthesized from established software engineering literature by an RE expert (last author). The functional and non-functional requirement definitions are derived from Glinz’s [19] summary of the literature definitions, which characterizes functional requirements in terms of the essential functions a system must perform, the services it must offer, and the behaviours it must exhibit under specified conditions—focusing on the inputs (stimuli), outputs (responses), and the behavioural relationships between them. The quality requirement definitions are synthesized from quality-modeling literature and standards [16, 35], expressing how well a system or service should execute an intended function through product quality aspects (e.g., functional suitability, reliability, performance, efficiency, usability, maintainability, security, compatibility, portability) and quality in use aspects (e.g., satisfaction, effectiveness, freedom from risk, context coverage). The security requirement definitions are derived from the security requirements engineering literature and standards [1, 20, 45], characterizing security requirements as prescriptive constraints imposed on a system’s functional behaviour to operationalize its security goals—restricting how functions are performed to prevent, detect, or recover from harm, while specifying security policies and addressing risks, threats, and assets. The non-functional, non-quality, and non-security definitions are obtained by negating their functional, quality, and security counterparts, respectively. These definitions capture the nuanced distinctions recognized in the domain, such as differentiating sub-categories of quality requirements (e.g., performance, security, usability). By grounding the initial prompt in domain knowledge, the LLM is provided with richer semantic context from the outset. In both cases, the definitions are subject to iterative refinement during the optimization process: at each iteration, the BT-APE mechanism may edit, expand, or restructure the class definitions based on misclassified and correctly classified examples from the training set 𝐷 pool . The goal of introducing these different definitions is to check whether a more informed initialization—rooted in domain literature—leads to superior classification performance compared to uninformed starting point, and whether this advantage persists after multiple rounds of optimization. All the prompt structures and definitions are given in Appendix F. 3.6
Inference-time voting protocol
The protocol described in this section is not specific to BT-APE; it is an evaluation safeguard applied uniformly to all prompting strategies (zero-shot, few-shot, CoT, CoT+few-shot, PE2, and BT-APE) whenever a prompt is scored on 𝐷𝑣𝑎𝑙 or 𝐷𝑡𝑒𝑠𝑡, so that comparisons across strategies are made under identical conditions. To mitigate the run-to-run variability of LLM outputs, we adopt a majority voting strategy during inference. Although we set the decoding temperature to 0, identical prompts can still yield different outputs across runs due to stochastic sampling at non-zero temperature settings, GPU nondeterminism, and request batching at the inference backend [36]. For each classification instance, the model is therefore executed three times with the same prompt, and the final label is assigned by majority vote: the class predicted in at least two out of three runs is selected as the final output. This J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
BT-APE: A Computationally Light Backtracking Approach to Automatic Prompt Engineering for Requirements Classification
111:13
protocol applies uniformly to baseline strategies and to the in-loop validation scoring of BT-APE (Algorithm 1, line 10) and PE2 (Algorithm 2). 4 4.1
Research Design Research Questions
The research design is guided by the following research questions (RQs): • RQ1: What is the performance of BT-APE in requirements classification compared to standard prompt engineering approaches? This question aims to evaluate the overall effectiveness of BT-APE relative to standard prompt engineering methods in the context of requirements classification. To answer this question, 1) we assess BT-APE’s performance across different LLMs and datasets using descriptive statistics (e.g., mean, standard deviation) for key metrics such as weighted-F1 score in comparison to other baseline methods. 2) We then conduct statistical significance testing to compare BT-APE results against the results obtained by the baseline methods. This allows us to determine whether BT-APE offers a meaningful improvement over manual or fixed prompt designs. • RQ2: What is the influence of the choice of dataset and LLM on the performance of BT-APE? This question aims to statistically assess whether the selected datasets and LLMs have a significant impact on the performance of the BT-APE process. To answer it, we execute BT-APE across the three classification tasks using each of the five LLMs and collect the resulting weighted-F1 scores, yielding one value per (dataset, LLM) combination. We then apply distribution-free statistical tests to determine whether performance differences across datasets and across LLMs are statistically significant, and report a rank-based effect size to quantify the strength of each factor. This analysis enables us to assess the individual effects of datasets and LLMs on BT-APE effectiveness. • RQ3: What are the defining characteristics of optimal prompts, and how do these emerge and evolve through BT-APE iterations? This question identifies the characteristics of effective prompts by analysing how they evolve across BT-APE iterations. We extract lexical (sentence count, word count, lexical diversity), syntactic (verb count, syntactic complexity), and semantic features (ambiguity score, semantic drift) from every prompt generated during the BT-APE process, and log them together with the validation weighted-F1 score of the prompt that produced them. Because each prompt is conditioned on its predecessor, observations within a (dataset, LLM) trajectory are not independent. We therefore analyse the data with a linear mixed-effects model (LMM) — prompt features as fixed effects, a random intercept per trajectory — so that coefficients estimate the within-trajectory association between each feature and performance, separated from between-configuration variance. Full model specification, robustness checks, hypotheses, and effect-size reporting are given in the statistical test design. One interpretive caveat is integral to the research question rather than to the test design: semantic drift (𝑆𝐷) is by construction a property of consecutive prompts, not of a prompt in isolation. A positive coefficient on 𝑆𝐷 would characterise successful search dynamics, not actionable guidance for designing a static prompt. We therefore separate state features (length, verb count, punctuation, lexical diversity, syntactic complexity, ambiguity) from the transition feature (𝑆𝐷), and restrict design claims to the former. • RQ4: To what extent does BT-APE-Informed influence classification performance compared to i) BT-APE-Uninformed and ii) how do both approaches perform relative to their respective best baseline models? This question examines the effect of class definition quality on the BT-APE process by J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
111:14
Zadenoori et al.
comparing two variants: BT-APE-Uninformed and BT-APE-Informed. To answer this, both variants are evaluated across the same datasets and LLMs under identical experimental conditions. Their performance is compared using key metrics such as Weighted 𝐹 1 score with statistical significance testing applied to assess whether BT-APE-Informed yields a meaningful improvement over BT-APE-Uninformed. In addition, each variant is compared against its respective best-performing baseline to determine how much improvement is achieved relative to standard prompt engineering approaches. This helps disentangle whether gains are driven primarily by the quality of the initial class definitions or by the iterative optimization process itself. Overall, this analysis isolates the role of class definitions as a design variable and evaluates whether domain-informed definitions provide a consistent advantage, or whether iterative optimization can compensate for simpler starting points. 4.2
Shared Experimental Settings
Tasks & Datasets. We evaluate BT-APE on three requirements classification tasks, each representing a distinct and well-studied problem in requirements engineering: • Functional-Quality classification based on the PROMISE Refined: In this task, we consider four binary classification tasks: Functional, Only Functional, Quality, and Only Quality. Specifically, this means that each data point should be evaluated solely on whether it meets functional requirements, quality requirements, or both. For every data point, we treat Functional and Quality as two separate ground-truth labels. The Only Functional task is then defined as instances that are labeled as Functional but not Quality, while the Only Quality task covers instances labeled as Quality but not Functional. • Functional–Non-Functional Binary Classification: Distinguishing between functional and Not-Functional requirements. This task addresses the fundamental separation between what a system should do and how well it should perform. • Security Binary Classification: Determining whether a requirement is security-related or not. This task targets a single quality concern and is particularly relevant for safety- and security-critical systems. We selected three well-established requirements datasets to represent the above tasks. These datasets have been extensively utilized in prior research involving machine learning and language models for RE, such as in [4, 14, 21, 26, 29]. A summary is presented in Table 1. Table 1. Overview of the Datasets Used in the Study. Main Classes
Sources
PROMISE (NFR)
Dataset
# Reqs. 625
255 Functional Requirements (FR), 370 Non-Functional Requirements (NFR).
Developed by Cleland-Huang et al.; used by Kurtanović and Maalej, Hey et al., and Alhoshan et al.
PROMISE (Refined)
625
310 Functional (FR), 230 is-only Functional (FR_only). 382 Quality (QA), 302 is-only Quality (Q_only)
Developed by Dalpiaz et al.; includes reclassification of PROMISE; used by Hey et al. and Alhoshan et al.
SecReq
510
187 Security-related (Sec), 323 Non-security (NSec)
Developed by Knauss et al.; based on ePurse, CPN, and GPS; used by Varenov et al. and Kobilica et al.
• PROMISE NFR Dataset: Developed by Cleland-Huang et al. [12, 13], this dataset comprises 625 requirements, including 255 FRs and 370 NFRs. This dataset has been widely adopted in the literature, including by Kurtanović and Maalej [29], Hey et al. [21], and Alhoshan et al. [4]. J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
BT-APE: A Computationally Light Backtracking Approach to Automatic Prompt Engineering for Requirements Classification
111:15
• PROMISE Refined Dataset: Introduced by Dalpiaz et al. [14], this dataset re-annotates the PROMISE NFR dataset. For binary classification, requirements are labeled as Quality (382) vs. non-Quality (243), and (302) labeled as quality only; and Functional (310) vs. non-Functional (315), and (230) labeled as functional only requirements. This dataset has been employed in studies such as [4, 21]. • SecReq Dataset: Created by Knauss et al. [26, 27], the SecReq dataset contains 510 requirements, split into 187 security-related and 323 non-security-related instances. The data were collected from three projects: Common Electronic Purse (ePurse), Customer Premises Network (CPN), and Global Platform Specification (GPS). It has been utilized in multiple studies, including [28, 49]. LLMs Selection. To select a representative set of instruction-tuned LLMs with approximately 7–8 billion parameters, we consulted the Hugging Face Open LLM Leaderboard1 as a reference for identifying widely used open-source models. The selection was guided by model availability, parameter scale, organisational diversity, and architectural characteristics rather than reported benchmark performance. Our goal is not to identify the single best-performing model on requirements classification, but to test whether BT-APE generalises across architectures and whether it consistently beats classical prompting baselines; using models that span different organisations, attention mechanisms, and pretraining corpora gives us a more honest stress test of generalisation than concentrating on top-ranked models from a single family. The 7–8B parameter range is chosen because models of this size can be hosted locally on a single commodity GPU, which reflects the practical RE setting where requirements confidentiality discourages reliance on hosted proprietary APIs [57]. Based on these criteria, we selected five models developed by different research organizations: Table 2. Overview of selected instruction-tuned LLMs used in this study. Mecha- Pretraining/Instruction Tasks
Organization
Multilingual corpora, code, instruction tuning MQA English web text, instruction data Scaled-dot attention Business text, code, domain (factual) adaptation Sliding Window Atten- Instruction datasets, reasontion ing tasks GQA, RoPE Multilingual corpora, SFT tasks
Alibaba Cloud
Model
Parameters Attention nism
Qwen2
7B
Falcon3
7B
Granite-3.2
8B
Ministral
8B
LLaMA-3
8B
RoPE, MQA
TII (UAE) IBM Research Mistral AI Meta AI
• Qwen2-7B-Instruct (Alibaba Cloud): employs Rotary Positional Embeddings combined with Multi-Query Attention to support efficient attention computation. It is pretrained on multilingual corpora and programming code and further refined using human-aligned instruction datasets. • Falcon3-7B-Instruct (Technology Innovation Institute): uses Multi-Query Attention to reduce inference-time memory requirements. Its training data primarily consists of largescale English web text and curated instruction-following datasets. 1 https://huggingface.co/spaces/open-llm-leaderboard/open_llm_leaderboard
J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
111:16
Zadenoori et al.
• Granite-3.2-8B-Instruct (IBM Research): applies optimized scaled dot-product attention with a focus on factual grounding. It is trained on business-oriented text, programming code, and domain-specific adaptation tasks. • Ministral-8B-Instruct-2410 (Mistral AI): incorporates Sliding Window Attention to limit attention to local contexts and improve computational efficiency. It is trained on instructionfollowing datasets and reasoning-oriented benchmarks. • Meta-Llama-3-8B-Instruct (Meta AI): adopts Grouped-Query Attention together with Rotary Positional Embeddings to balance efficiency and representational capacity. Its pretraining relies on large-scale multilingual corpora and supervised fine-tuning on human-aligned datasets. Table 2 summarizes the main technical characteristics of the selected models, including parameter size, attention mechanisms, pretraining and instruction tasks, and organizational origin. These descriptions provide contextual background for the experimental setup without presupposing differences in task performance. Evaluation Metrics. We used four standard evaluation metrics: Precision (𝑃), Recall (𝑅), Weighted F1 Score (𝑤𝐹 1 ). These metrics are well-suited for imbalanced classification tasks and allow us to evaluate both general accuracy and recall-oriented performance. • Precision (𝑃): The proportion of correctly predicted instances for a given class among all instances predicted as belonging to that class. 𝑇𝑃 𝑇𝑃 + 𝐹𝑃 • Recall (𝑅): The proportion of correctly predicted instances for a given class among all actual instances of that class. 𝑇𝑃 𝑅= 𝑇𝑃 + 𝐹𝑁 • Weighted F1 Score (𝑤𝐹 1 ): The harmonic mean of precision and recall, computed for each class and averaged using the number of true instances (support) as weights. ∑︁ 2 · 𝑃𝑐 · 𝑅𝑐 𝑤𝐹 1 = 𝑤𝑐 · 𝑃𝑐 + 𝑅𝑐 𝑐 ∈𝐶 𝑃=
ìIn the above equations, 𝑇 𝑃, 𝐹 𝑃, and 𝐹 𝑁 denote true positives, false positives, and false negatives, respectively; 𝑤𝑐 represents the support (i.e., the proportion of instances) for class 𝑐, and 𝐶 is the set of all target classes. 4.3
Prompt Baselines Selection
We compare our approach against five widely adopted prompting strategies that together cover the standard spectrum of techniques used to elicit classification performance from LLMs without taskspecific fine-tuning: four in-context learning baselines of increasing sophistication, and one APE baseline. These baselines are selected because they are (i) model-agnostic and reproducible across both large and small language models, (ii) computationally lightweight and therefore compatible with our SLM deployment setting, and (iii) established as canonical reference points in recent RE and NLP classification studies [6]. The five baselines are: • Zero-shot prompting: The model receives only a task description and label definitions, with no labeled examples. This baseline measures the model’s ability to perform the classification task purely from its pretrained knowledge and the natural-language specification of the task. • Few-shot prompting: The model is provided with a small set of labeled input–output examples alongside the task description. This baseline isolates the contribution of demonstration-based J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
BT-APE: A Computationally Light Backtracking Approach to Automatic Prompt Engineering for Requirements Classification
111:17
in-context learning, allowing us to measure how much performance improves when the model is exposed to representative instances of each requirement category. • Chain-of-Thought (CoT) prompting: The model is explicitly instructed to generate intermediate reasoning steps before producing the final output. This baseline tests whether eliciting structured reasoning improves classification on requirements that demand multi-step interpretation, such as distinguishing functional from non-functional aspects in compound statements. • CoT with Few-shot prompting: The model receives multiple labeled examples, each accompanied by an explicit reasoning trace and the final label. This baseline combines demonstrationbased learning with reasoning elicitation and represents the strongest non-optimised prompting configuration commonly reported in the literature. • PE2 (APE) [53]: The prompt is iteratively refined by a meta-prompted LLM conditioned on the top-𝑛 historical prompts with their validation weighted-F1 scores and a batch of misclassifications observed on a held-out pool. Unlike the four baselines above, which keep the prompt fixed, PE2 actively searches the prompt space using the same iteration budget and evaluation protocol as our method. This baseline is the most directly comparable reference point for our approach, since both methods are single-trajectory, history-aware APE procedures driven by errors on a held-out set; its inclusion is what allows us to attribute any performance gap to our three algorithmic contributions—bounded back-tracking, balanced four-tuple example selection, and majority-voted F1—rather than to the use of prompt optimisation in general. Full algorithmic and implementation details, together with a precise enumeration of the differences from our method, are given in Appendix B (Algorithm 2). The exact prompt templates used for each baseline are provided in the replication package [54]. 4.4
Experimental Design for RQ1
Statistical Significance.2 To assess whether the performance differences between each baseline prompting strategy and the proposed BT-APE approach are statistically significant, we analyse the per-cell differences in 𝑤𝐹 1 (i.e., Δ = 𝑤𝐹 1,BT-APE − 𝑤𝐹 1,Baseline ). All differences across datasets and LLMs are pooled for each baseline strategy. We then conduct a non-parametric Wilcoxon signed-rank test to evaluate whether BT-APE achieves a higher mean 𝑤𝐹 1 than the baseline. All tests are performed at a significance level of 𝛼 = 0.05, with 𝑝-values adjusted using the Holm–Bonferroni procedure to account for multiple baseline comparisons. For each comparison between BT-APE and a baseline strategy, the following hypotheses are defined: RQ1 • 𝐻 1,0 : The mean difference in performance (𝑤𝐹 1 ) between BT-APE and the baseline strategy is zero (Δ = 0). RQ1 • 𝐻 1,𝐴 : BT-APE achieves a higher mean performance (𝑤𝐹 1 ) than the baseline strategy (Δ > 0). Effect Size and Interpretation. We report the mean difference in 𝑤𝐹 1 (Δ) with 95% confidence intervals. This statistic is centred at zero when there is no improvement: • Δ = 0 indicates no systematic difference. • Positive values indicate that BT-APE outperforms the baseline. • Negative values indicate that the baseline outperforms BT-APE. 2 Notation for hypotheses. Throughout Sections 4.4–4.7, we denote hypotheses using 𝐻 RQ𝑛 for the null and 𝐻 RQ𝑛 for the 𝑘,0 𝑘,𝐴 RQ1 alternative, where 𝑛 is the research question and 𝑘 indexes the hypothesis within that question. For example, 𝐻 1,0 is the RQ2 first null hypothesis under RQ1 and 𝐻 2,𝐴 the second alternative hypothesis under RQ2.
J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
111:18
Zadenoori et al.
√ Effect size 𝑟 is computed as 𝑟 = 𝑍 / 𝑁 , where 𝑍 is the standardised Wilcoxon test statistic and 𝑁 is the number of observations. Magnitudes are interpreted as: negligible (𝑟 < 0.10), small (0.10 ≤ 𝑟 < 0.30), moderate (0.30 ≤ 𝑟 < 0.50), and large (𝑟 ≥ 0.50) [47]. 4.5
Experimental Design for RQ2
Factors Analysis. To address RQ2, we investigate how the performance of BT-APE varies as a function of two independent variables—Datasets/Tasks and LLMs—as well as their interaction. The final BT-APE results consist of one 𝑤𝐹 1 value per (Dataset, LLM) combination, yielding a 3 × 5 design with 𝑛 = 15 observations. • Datasets/Tasks. We test whether performance (𝑤𝐹 1 ) differs significantly across requirements classification tasks (Security, Functional, and Quality). • LLMs. We test whether performance (𝑤𝐹 1 ) differs significantly across the selected LLMs. Statistical Significance. We first assess the normality assumption with the Shapiro–Wilk test. Given the small sample and borderline normality, we adopt distribution-free Friedman tests for the two main effects rather than relying on the assumptions of parametric ANOVA. We test the dataset effect using LLMs as blocks, and the LLM effect using datasets as blocks. All tests are conducted at a significance level of 𝛼 = 0.05. The following hypotheses are defined: • Dataset/Task effect. RQ2 – 𝐻 1,0 : There is no statistically significant difference in 𝑤𝐹 1 across datasets. RQ2
– 𝐻 1,𝐴 : There is a statistically significant difference in 𝑤𝐹 1 across datasets. • LLM effect. RQ2 – 𝐻 2,0 : There is no statistically significant difference in 𝑤𝐹 1 across LLMs. RQ2
– 𝐻 2,𝐴 : There is a statistically significant difference in 𝑤𝐹 1 across LLMs. Effect Size and Interpretation. We report Kendall’s 𝑊 as the effect size for each Friedman test, which ranges from 0 (no agreement among blocks) to 1 (perfect agreement). Larger values indicate a stronger and more consistent factor effect across the blocking variable. As the interaction is not estimable under a single-replicate design, we do not test it formally; where the cell-level results suggest task-dependent model behaviour, we describe it descriptively. 4.6
Experimental Design for RQ3
Prompt Feature Extraction. We extract and log a set of lexical, syntactic, and semantic features from each prompt generated during BT-APE iterations. These features are defined and computed as follows. a) Lexical Features. • Sentence Count (𝑆𝐶): The number of sentences in the prompt, measured using sentence segmentation. 𝑆𝐶 = Number of sentences in 𝑃 • Word Count (𝑊 𝐶): The total number of words or tokens in the prompt. ( 𝑛 ∑︁ 1, if 𝑤𝑖 is a word 𝑊𝐶 = 𝛿 (𝑤𝑖 ), 𝛿 (𝑤𝑖 ) = 0, otherwise 𝑖=1 • Punctuation/Markers Count (𝑃𝑀): The number of structural markers such as colons, dashes, or line breaks. ( ∑︁ 1, if 𝑐 ∈ {:, -, ., \n, . . .} 𝑃𝑀 = 𝛿 (𝑐), 𝛿 (𝑐) = 0, otherwise 𝑐 ∈𝑃 J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
BT-APE: A Computationally Light Backtracking Approach to Automatic Prompt Engineering for Requirements Classification
111:19
• Lexical Diversity (𝐿𝐷): The ratio of unique words to total words, indicating vocabulary richness. |Unique(𝑤 1, 𝑤 2, . . . , 𝑤𝑛 )| 𝐿𝐷 = 𝑊𝐶 b) Syntactic Features. • Verb Count (𝑉 𝐵): The number of verbs in the prompt, identified via part-of-speech tagging. 𝑛 ∑︁ 𝑉𝐵 = 𝛿 (POS(𝑤𝑖 ) = VERB) 𝑖=1
• Syntactic Complexity (𝑆𝐶𝑥): The average depth of the dependency parse tree over all tokens in the prompt. 𝑛 1 ∑︁ 𝑆𝐶𝑥 = depth(𝑤𝑖 ) 𝑛 𝑖=1 where depth(𝑤𝑖 ) denotes the number of dependency links from word 𝑤𝑖 to the root. c) Semantic Features. • Ambiguity Score (𝐴𝑆): quantifies the vagueness of a prompt based on the presence of ambiguous or underspecified terms, commonly referred to as “smelly” words (e.g., some, many, etc., maybe, often, unclear, various). The score is computed heuristically as: 𝑊𝐶
𝐴𝑆 =
1 ∑︁ 𝛿 (𝑤𝑖 ∈ 𝐷 amb ) 𝑊 𝐶 𝑖=1
where: – 𝑊 𝐶 is the total word count of the prompt, – 𝑤𝑖 is the 𝑖 th word in the prompt, – 𝐷 amb is a predefined dictionary of ambiguity-inducing terms, – 𝛿 (·) is an indicator function that returns 1 if 𝑤𝑖 ∈ 𝐷 amb , and 0 otherwise. • Semantic Drift (𝑆𝐷): quantifies the semantic change between the current prompt and the immediately preceding one, computed as the cosine distance between their embedding vectors. For a sequence of 𝑛 prompts, the drift at iteration 𝑖 is defined as: if 𝑖 = 1 0, 𝑆𝐷𝑖 = 𝑒®𝑖 · 𝑒®𝑖 −1 , if 𝑖 > 1 1 − ∥𝑒®𝑖 ∥ ∥𝑒®𝑖 −1 ∥ where 𝑒®𝑖 and 𝑒®𝑖 −1 are the embedding vectors of the prompts at iterations 𝑖 and 𝑖 −1, respectively. This formulation captures the magnitude of semantic shift introduced at each step in the BT-APE process. All of these features (lexical, syntactic, and semantic) are tracked across all BT-APE iterations to study how prompt structure changes over time and how such changes correlate with model performance improvements. We further distinguish between state features, which describe a prompt in isolation (𝑆𝐶, 𝑊 𝐶, 𝑃𝑀, 𝐿𝐷, 𝑉 𝐵, 𝑆𝐶𝑥, 𝐴𝑆), and transition features, which describe a change between consecutive prompts (𝑆𝐷). This distinction matters for interpretation: a within-trajectory association between a state feature and performance can plausibly motivate prompt-design guidance, whereas an association involving 𝑆𝐷 characterises the dynamics of successful search rather than properties of a static prompt. Statistical Model. The prompts generated across BT-APE iterations are not independent observations. Within a single (dataset, LLM) trajectory, every prompt is conditioned on its predecessor, shares the same proposer, and inherits the same starting point; across trajectories, baseline performance J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
111:20
Zadenoori et al.
differs systematically with task difficulty and model capability (as established in RQ2). Pooling all prompts into an ordinary least-squares regression with 𝑤𝐹 1 as the response would therefore conflate within-trajectory variance—how performance changes as a single search evolves—with between-configuration variance, and would overstate the precision of the resulting coefficients by treating non-independent observations as independent. To respect this nested structure, we estimate a linear mixed-effects model (LMM) in which prompt features enter as fixed effects and a random intercept is fitted for each (dataset, LLM) trajectory: ∑︁ 𝑤𝐹 1,𝑖 𝑗 = 𝛽 0 + 𝛽𝑘 𝑥𝑘,𝑖 𝑗 + 𝑢 𝑗 + 𝜀𝑖 𝑗 , 𝑢 𝑗 ∼ N (0, 𝜎𝑢2 ), 𝜀𝑖 𝑗 ∼ N (0, 𝜎𝜀2 ), 𝑘
where 𝑖 indexes the iteration within trajectory 𝑗 ∈ {1, . . . , 15}, 𝑥𝑘,𝑖 𝑗 is the value of the 𝑘-th prompt feature at iteration 𝑖 of trajectory 𝑗, 𝑢 𝑗 is the random intercept absorbing configuration-level differences in baseline 𝑤𝐹 1 , and 𝜀𝑖 𝑗 is the residual. The fixed-effect coefficients 𝛽𝑘 therefore estimate the within-trajectory association between each prompt feature and performance, after removing the contribution of the underlying (dataset, LLM) configuration. The model is estimated by restricted maximum likelihood (REML), and all features are standardised to zero mean and unit variance prior to fitting so that coefficient magnitudes are directly comparable. Robustness Check on Terminal Prompts. As a complementary analysis that is independent of trajectory dynamics by construction, we also fit an ordinary least-squares regression on the terminal prompts 𝑝 ∗ of each of the 15 trajectories (𝑛 = 15). The transition feature 𝑆𝐷 is excluded from this analysis as it is not defined for a single prompt. This terminal-prompt regression has limited statistical power but provides a sanity check: a feature whose within-trajectory effect under the LMM is contradicted by its sign on terminal prompts is unlikely to constitute reliable design guidance. We therefore report a feature as a robust correlate of effective prompts only when its LMM coefficient is statistically significant and its sign agrees with the terminal-prompt regression. Hypotheses. All tests are conducted at a significance level of 𝛼 = 0.05, with Holm–Bonferroni correction applied across the feature set to control the family-wise error rate. RQ3
• 𝐻 1,0 : After accounting for between-trajectory variance, prompt features have no statistically significant within-trajectory effect on 𝑤𝐹 1 (𝛽𝑘 = 0 for all 𝑘). RQ3 • 𝐻 1,𝐴 : At least one prompt feature has a statistically significant within-trajectory effect on 𝑤𝐹 1 . Effect Size and Interpretation. We report standardised fixed-effect coefficients 𝛽ˆ𝑘 with 95% confidence intervals for each feature. Positive coefficients indicate that, within a trajectory, an increase in the feature is associated with higher 𝑤𝐹 1 ; negative coefficients indicate the converse. The absolute magnitude of 𝛽ˆ𝑘 reflects the relative strength of the feature’s within-trajectory contribution. 2 measures the proportion of At the model level, we report three quantities. The marginal 𝑅𝑚 variance in 𝑤𝐹 1 explained by the fixed effects alone, and is the appropriate analogue of the OLS 𝑅 2 for the prompt-feature claim. The conditional 𝑅𝑐2 measures the proportion explained by fixed and random effects jointly, and indicates the total fit of the model. The intra-class correlation coefficient (ICC), 𝜎2 ICC = 2 𝑢 2 , 𝜎𝑢 + 𝜎𝜀 quantifies the share of residual variance attributable to between-configuration differences rather than to within-trajectory prompt characteristics; a high ICC would indicate that most of the variation in 𝑤𝐹 1 is configuration-driven and that within-trajectory feature effects, however statistically 2 , significant, account for a comparatively small share of overall performance variation. Together, 𝑅𝑚 J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
BT-APE: A Computationally Light Backtracking Approach to Automatic Prompt Engineering for Requirements Classification
111:21
𝑅𝑐2 , and the ICC provide a more honest accounting of where the explanatory power of the model lies than a single pooled 𝑅 2 would. As noted above, we treat 𝑆𝐷 separately in the interpretation: a significant within-trajectory coefficient on 𝑆𝐷 is described as a property of successful optimisation trajectories rather than as actionable guidance for designing a static prompt. Actionable design claims are restricted to state features whose coefficients are stable across the LMM and the terminal-prompt regression. 4.7
Experimental Design for RQ4
Class Definitions. As introduced in Section 3.5, we define two initialisation strategies for the prompt optimisation process. In BT-APE-Informed, the initial prompt is seeded with fine-grained class definitions curated from requirements engineering literature and standards. In BT-APE-Uninformed, no predefined class definitions are provided; instead, the algorithm begins with simple, minimal descriptions and iteratively refines them throughout the optimisation process. This design allows us to assess two complementary aspects: (1) whether domain-grounded definitions offer a measurable advantage as a starting point, and (2) whether the iterative optimisation is capable of discovering effective definitions independently, without relying on prior domain knowledge. Statistical Significance. To assess whether the performance differences between BT-APE-Uninformed and BT-APE-Informed are statistically significant, we analyse two complementary dimensions. Dimension 1: Final Performance Comparison. We analyse the per-cell differences in final optimised 𝑤𝐹 1 (i.e., Δfinal = 𝑤𝐹 1,BT-APE-Informed −𝑤𝐹 1,BT-APE-Uninformed ). All differences across datasets and LLMs are pooled. We then conduct a Wilcoxon signed-rank test to evaluate whether BT-APE-Informed achieves a higher mean final 𝑤𝐹 1 than BT-APE-Uninformed. The test is performed at a significance level of 𝛼 = 0.05. For this comparison, the following hypotheses are defined: RQ4
• 𝐻 1,0 : The mean difference in final performance (𝑤𝐹 1 ) between BT-APE-Informed and BTAPE-Uninformed is zero (Δfinal = 0). RQ4 • 𝐻 1,𝐴 : BT-APE-Informed achieves a higher mean final performance (𝑤𝐹 1 ) than BT-APEUninformed (Δfinal > 0). Dimension 2: Improvement-over-Baseline Comparison. Since each variant has its own independent baseline (fine-grained class definitions for BT-APE-Informed vs. minimal descriptions for BT-APEUninformed), we compute the per-cell gain for each variant relative to its own starting point: ΔInformed = 𝑤𝐹 1,Informed-Opt − 𝑤𝐹 1,Informed-Baseline ΔUninformed = 𝑤𝐹 1,Uninformed-Opt − 𝑤𝐹 1,Uninformed-Baseline We then calculate the difference in gains: 𝛿 gain = ΔInformed − ΔUninformed A separate Wilcoxon signed-rank test is applied to 𝛿 gain across all (dataset, LLM) pairs to evaluate whether the two variants improve equally over their respective baselines. The hypotheses for this dimension are: RQ4 • 𝐻 2,0 : The mean difference in gains (𝛿 gain ) between BT-APE-Informed and BT-APEUninformed is zero, i.e., both variants improve equally over their own baselines. RQ4 • 𝐻 2,𝐴 : The mean difference in gains (𝛿 gain ) is not zero, i.e., one variant achieves greater relative improvement from its baseline than the other. Effect Size and Interpretation. For both dimensions, we report the mean difference (Δfinal and 𝛿 gain respectively) with 95% confidence intervals, following the same interpretation benchmarks defined in RQ1. This dual analysis allows us to isolate the contribution of class definitions as a design variable and assess: (a) whether domain-grounded definitions provide a lasting advantage in final J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
111:22
Zadenoori et al.
performance, and (b) whether the iterative optimisation compensates for simpler starting points by achieving comparable or greater relative improvement from a lower baseline.
5
Experimental Results
In this section, we present the results of the classification experiments conducted on three datasets: Refined Promise, Promise NFR, and SecReq. Performance is reported using weighted F1 (𝑤𝐹 1 ) score for the overall (average) results, and per-class F1 score for the class-specific breakdowns.
Refined Promise Dataset Results. Table 3 presents the classification results for the Refined Promise dataset, which includes classes for Functional (F), Quality (Q), Only Functional (onlyF), and Only Quality (onlyQ).
Model
Qwen/Qwen2-7B-Instruct
Falcon3-7B-Instruct
Granite-3.2-8B-Instruct
Ministral-8B-Instruct-2410
Llama-3-8B-Instruct
Strategy Zero-shot Few-shot CoT CoT + Few-shot APE-PE2 BT-APE Zero-shot Few-shot CoT CoT + Few-shot APE-PE2 BT-APE Zero-shot Few-shot CoT CoT + Few-shot APE-PE2 BT-APE Zero-shot Few-shot CoT CoT + Few-shot APE-PE2 BT-APE Zero-shot Few-shot CoT CoT + Few-shot APE-PE2 BT-APE
Average wF1 0.413 0.500 0.487 0.547 0.587 0.595 0.125 0.559 0.260 0.635 0.620 0.607 0.463 0.515 0.441 0.476 0.472 0.477 0.455 0.594 0.362 0.446 0.646 0.637 0.212 0.266 0.283 0.393 0.540 0.551
F wF1 0.421 0.390 0.410 0.537 0.583 0.579 0.082 0.677 0.622 0.729 0.645 0.656 0.557 0.672 0.572 0.649 0.536 0.529 0.569 0.682 0.481 0.616 0.642 0.655 0.297 0.153 0.274 0.616 0.683 0.691
Q wF1 0.594 0.615 0.643 0.636 0.679 0.685 0.185 0.544 0.082 0.672 0.670 0.662 0.256 0.260 0.144 0.557 0.325 0.337 0.195 0.458 0.051 0.296 0.672 0.676 0.075 0.573 0.473 0.296 0.305 0.299
onlyF wF1 0.421 0.640 0.640 0.640 0.691 0.679 0.082 0.677 0.185 0.729 0.658 0.663 0.557 0.672 0.572 0.215 0.678 0.667 0.569 0.682 0.481 0.692 0.647 0.633 0.297 0.234 0.274 0.535 0.625 0.629
onlyQ wF1 0.215 0.356 0.256 0.374 0.444 0.437 0.152 0.337 0.151 0.409 0.437 0.446 0.483 0.455 0.477 0.483 0.381 0.373 0.488 0.554 0.436 0.181 0.590 0.585 0.181 0.104 0.112 0.123 0.571 0.585
Table 3. Classification results for the Refined Promise dataset (weighted F1).
J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
BT-APE: A Computationally Light Backtracking Approach to Automatic Prompt Engineering for Requirements Classification Model
Qwen/Qwen2-7B-Instruct
Falcon3-7B-Instruct
Granite-3.2-8B-Instruct
Ministral-8B-Instruct-2410
Llama-3-8B-Instruct
Strategy Zero-shot Few-shot CoT CoT + Few-shot APE-PE2 BT-APE Zero-shot Few-shot CoT CoT + Few-shot APE-PE2 BT-APE Zero-shot Few-shot CoT CoT + Few-shot APE-PE2 BT-APE Zero-shot Few-shot CoT CoT + Few-shot APE-PE2 BT-APE Zero-shot Few-shot CoT CoT + Few-shot APE-PE2 BT-APE
Average wF1 0.749 0.726 0.668 0.749 0.838 0.847 0.642 0.708 0.753 0.754 0.843 0.831 0.703 0.720 0.708 0.774 0.816 0.820 0.377 0.722 0.722 0.722 0.853 0.847 0.716 0.680 0.679 0.717 0.780 0.792
F wF1 0.750 0.730 0.609 0.750 0.858 0.847 0.574 0.706 0.751 0.752 0.814 0.828 0.711 0.705 0.701 0.754 0.819 0.812 0.094 0.721 0.721 0.727 0.838 0.846 0.723 0.695 0.699 0.723 0.791 0.778
111:23
NFR wF1 0.748 0.722 0.727 0.748 0.833 0.846 0.711 0.710 0.755 0.755 0.838 0.833 0.695 0.736 0.714 0.794 0.833 0.827 0.659 0.723 0.722 0.716 0.834 0.848 0.710 0.665 0.659 0.711 0.814 0.805
Table 4. Classification results for the Promise NFR dataset (weighted F1).
J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
111:24
Zadenoori et al.
Model
Qwen/Qwen2-7B-Instruct
Falcon3-7B-Instruct
Granite-3.2-8B-Instruct
Ministral-8B-Instruct-2410
Llama-3-8B-Instruct
Strategy Zero-shot Few-shot CoT CoT + Few-shot APE-PE2 BT-APE Zero-shot Few-shot CoT CoT + Few-shot APE-PE2 BT-APE Zero-shot Few-shot CoT CoT + Few-shot APE-PE2 BT-APE Zero-shot Few-shot CoT CoT + Few-shot APE-PE2 BT-APE Zero-shot Few-shot CoT CoT + Few-shot APE-PE2 BT-APE
Average wF1 0.651 0.818 0.843 0.843 0.937 0.945 0.848 0.836 0.825 0.848 0.952 0.947 0.819 0.766 0.871 0.836 0.848 0.859 0.814 0.814 0.787 0.797 0.935 0.922 0.886 0.862 0.867 0.886 0.857 0.864
Security wF1 0.468 0.736 0.778 0.778 0.919 0.908 0.789 0.774 0.750 0.789 0.896 0.903 0.789 0.672 0.825 0.774 0.797 0.783 0.738 0.738 0.745 0.715 0.863 0.872 0.842 0.807 0.817 0.847 0.800 0.795
Non-Security wF1 0.835 0.900 0.908 0.908 0.975 0.981 0.907 0.897 0.899 0.907 0.983 0.991 0.849 0.861 0.916 0.897 0.941 0.934 0.889 0.889 0.829 0.880 0.978 0.972 0.925 0.917 0.916 0.925 0.920 0.933
Table 5. Classification results for the Secreq dataset (weighted F1).
5.1
Quantitative Comparison: BT-APE vs. Baseline Prompting Strategies
Overall Performance Analysis: BT-APE vs. Baselines. Figure 2 presents the average F1 obtained by each of the five instruction-tuned LLMs under every prompting strategy, split into three panels corresponding to the three requirements-classification datasets. Within each panel, the six grouped bars per model show Zero-shot, Few-shot, CoT, CoT+Few-shot, APE-PE2, and BT-APE, and a ⋆ marks the strategy that achieves the highest average F1 for that model. Refined Promise Dataset: BT-APE is the best strategy for two of the five models, while APE-PE2 emerges as the strongest baseline in three of them. For Qwen2-7B, BT-APE achieves an average F1 of 0.595, +0.008 above the strongest baseline (APE-PE2 at 0.587) and +0.048 above the best classical baseline (CoT+Few-shot at 0.547). The largest margin on this dataset is on Llama-8B, where BT-APE attains 0.551, +0.011 over APE-PE2 (0.540) and +0.158 over the best classical baseline (CoT+Few-shot at 0.393). On Ministral-8B, APE-PE2 narrowly takes the top with 0.646, +0.009 above BT-APE (0.637) and +0.052 above the best classical baseline (Few-shot at 0.594). For the remaining two models the strongest baseline is a classical one: on Falcon3-7B, BT-APE (0.607) trails CoT+Few-shot (0.635) by −0.028, and on Granite-8B, BT-APE (0.477) trails Few-shot (0.515) by −0.038. Promise NFR Dataset: BT-APE and APE-PE2 jointly hold the top spot on all five models, with BT-APE leading on three (Qwen2-7B, Granite-8B, Llama-8B) and APE-PE2 on the other two (Falcon3-7B, Ministral-8B). The gap between the two is small in every case: +0.009 for Qwen2-7B (BT-APE 0.847 vs. APE-PE2 0.838), +0.004 for Granite-8B (0.820 vs. 0.816), +0.012 for Llama-8B (0.792 vs. 0.780), −0.012 for Falcon3-7B (0.831 vs. 0.843), and −0.006 for Ministral-8B (0.847 vs. 0.853). Both strategies decisively beat the simpler baselines, with the largest gain reaching +0.131 for APE-PE2 over Few-shot on Ministral-8B and +0.098 for BT-APE over Zero-shot on Qwen2-7B. J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
BT-APE: A Computationally Light Backtracking Approach to Automatic Prompt Engineering for Requirements Classification
111:25
SecReq Dataset: BT-APE is the best strategy on one of the five models, APE-PE2 on two, and a classical baseline on the remaining two. On Qwen2-7B, BT-APE reaches 0.945, +0.008 above APE-PE2 (0.937) and +0.102 above the best classical baseline (CoT at 0.843). On Falcon3-7B, APE-PE2 leads with 0.952—the highest average wF1 across all model–dataset combinations in the figure—narrowly above BT-APE (0.947, −0.005); the same pattern holds on Ministral-8B, where APE-PE2 (0.935) exceeds BT-APE (0.922) by +0.013 and improves over the best classical baseline (Zero-shot at 0.814) by +0.121. In the two remaining cases BT-APE is marginally below the strongest baseline: on Granite-8B, BT-APE (0.859) trails CoT (0.871) by −0.012, and on Llama-8B, BT-APE (0.864) trails Zero-shot (0.886) by −0.022. Two trends are immediately apparent from Figure 2. First, the two APE strategies—BT-APE and APE-PE2—together dominate the comparison, jointly accounting for the best result in 11 out of 15 model–dataset combinations and reaching up to 0.952 on SecReq (Falcon3-7B, APE-PE2) and 0.853 on Promise NFR (Ministral-8B, APE-PE2). The two methods trade places in tight margins—typically within ±0.013 of one another—suggesting that the two prompt-optimization procedures converge to a similar performance regime, with BT-APE marginally ahead overall (6 wins vs. 5 for APE-PE2 when both are considered). The few remaining best-strategy cases, such as CoT+Few-shot for Falcon3-7B and Few-shot for Granite-8B on Refined Promise, or CoT for Granite-8B and Zero-shot for Llama-8B on SecReq, involve classical baselines that nonetheless remain within a narrow margin of BT-APE. Second, performance is strongly conditioned by dataset difficulty: all models score substantially lower on the four-class Refined Promise task than on the binary Promise NFR and SecReq tasks, where most strategies already exceed 0.70 F1. Simpler prompting strategies are also far less stable; Zero-shot and CoT in particular collapse for some models (e.g. Falcon3-7B drops to 0.125 under Zero-shot on Refined Promise, and Ministral-8B to 0.377 under Zero-shot on Promise NFR), whereas BT-APE and APE-PE2 consistently lift the weakest configurations and narrow the gap between models. Overall, the results indicate that the choice of prompting strategy has a larger and more reliable effect on classification quality than the choice of model, with BT-APE—closely tracked by APE-PE2—offering the most robust performance across all three datasets. Summary of BT-APE vs. Baselines. Quantitatively, BT-APE matches or outperforms the strongest baseline (now including APE-PE2) in 6 out of 15 model–dataset combinations on average F1, and when APE-PE2 is set aside as the optimization-based peer, BT-APE matches or outperforms the best classical baseline (Zero-shot, Few-shot, CoT, CoT+Few-shot) in 11 out of 15 combinations. The mean improvement of BT-APE over the strongest baseline including APE-PE2 is essentially flat competitor—while the mean improvement of BT-APE over the best classical baseline rises to +0.059. The gains over classical baselines are most consistent on Promise NFR (+0.084 average improvement) and on SecReq (+0.055), while on the most difficult dataset, Refined Promise, BT-APE still wins two of five models but with a smaller average margin (+0.037) owing to two competitive classical baseline cases. In the configurations where BT-APE does not lead, the shortfall against the winning baseline—whether APE-PE2 or a classical one—is small (between −0.005 and −0.038) and BT-APE remains competitive throughout. These results establish BT-APE—together with its variant APE-PE2—as the most consistently strong prompting strategy relative to the simpler baselines. 5.2
Answers to RQ1
Results. BT-APE consistently outperforms the four classical baseline strategies across nearly all datasets and models, while remaining essentially tied with the optimization-based variant APE-PE2. As shown in Table 6, BT-APE achieves positive mean differences (Δ = 𝑤𝐹 1BT-APE − 𝑤𝐹 1Baseline ) ranging from +0.0492 to +0.1425 against the classical baselines, with effect sizes ranging from J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
111:26
Zadenoori et al.
Fig. 2. Average F1 of the five instruction-tuned LLMs across the six prompting strategies on the three requirements-classification datasets. The ⋆ marks the best-performing strategy for each model.
medium to large according to established benchmarks (negligible (𝑟 < 0.10), small (0.10 ≤ 𝑟 < 0.30), moderate (0.30 ≤ 𝑟 < 0.50), and large (𝑟 ≥ 0.50)). Statistical testing reveals that BT-APE significantly outperforms every classical baseline at the corrected significance level. Against APE-PE2, however, the mean difference collapses to +0.001 with a negligible effect size, indicating that the two automated prompt-engineering methods converge to comparable performance. J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
BT-APE: A Computationally Light Backtracking Approach to Automatic Prompt Engineering for Requirements Classification
111:27
Table 6. Summary of BT-APE performance compared to baseline strategies. Baseline Zero-shot FewShot COT COT + Few-shot APE-PE2
n 15 15 15 15 15
Mean Δ +0.1425 +0.1139 +0.1202 +0.1135 +0.0011
95% CI [+0.0867, +0.1983] [+0.0807, +0.1472] [+0.0836, +0.1568] [+0.0884, +0.1386] [ −0.0039, +0.0061]
Effect Size Large Large Large Large Negligible
Significant Yes Yes Yes Yes No
The Wilcoxon signed-rank test results demonstrate that BT-APE’s improvements over the four classical baselines are statistically significant. For Zero-shot, the mean improvement is Δ = +0.1425 (95% CI [0.0867, 0.1983], 𝑝 corrected = 0.000305). Similarly, BT-APE improves upon FewShot by Δ = +0.1139 (95% CI [0.0807, 0.1472], 𝑝 corrected = 0.001307) and upon COT by Δ = +0.1202 (95% CI [0.0836, 0.1568], 𝑝 corrected = 0.001335). The improvement over CoT + Few-shot is also significant (Δ = +0.1135, 95% CI [0.0884, 0.1386], 𝑝 corrected = 0.001953). These results lead us to reject the null hypothesis for all four classical baselines, confirming that BT-APE achieves a statistically significantly higher mean performance. For APE-PE2, by contrast, the test does not reject the null hypothesis (Δ = +0.0011, 95% CI [−0.0039, +0.0061], 𝑝 corrected > 0.05), indicating that BT-APE and APE-PE2 yield statistically indistinguishable performance on these tasks. Dataset-Level Analysis. Examining performance across individual datasets reveals interesting patterns. On the Refined Promise dataset, BT-APE demonstrates substantial improvements over all classical baselines, with mean Δ values of +0.1468 (Zero-shot), +0.1660 (FewShot), +0.1718 (COT), and +0.1286 (COT + Few-shot), but essentially matches APE-PE2 (Δ = +0.0004). The largest gains are observed against FewShot and COT, where improvements exceed +0.16. For the Promise NFR dataset, BT-APE again shows consistent superiority over the classical baselines, with mean Δ values of +0.1838 (Zero-shot), +0.1226 (FewShot), +0.1260 (COT), and +0.0984 (CoT + Few-shot), and once more matches APE-PE2 (Δ = +0.0014). Notably, the improvement over Zero-shot is particularly pronounced at +0.1838, indicating that BT-APE is especially valuable when no example prompts are provided. On the Secreq dataset, improvements over classical baselines are more modest but still positive: +0.0968 (Zero-shot), +0.0532 (FewShot), +0.0628 (COT), and +0.0492 (CoT + Few-shot), with APEPE2 again indistinguishable from BT-APE (Δ = +0.0016). The smaller effect sizes on this dataset may be attributed to the easy-to-understand nature of the binary classification task (Security vs. Non-Security), which is inherently less challenging than the other tasks. Nevertheless, BT-APE still achieves medium effect sizes across all four classical baselines. Per-Model Analysis. The detailed per-comparison results reveal that BT-APE’s superiority over the classical baselines is consistent across different LLM architectures, while its margin over APE-PE2 fluctuates narrowly around zero. For the Qwen/Qwen2-7B-Instruct model, BT-APE outperforms all four classical baselines across all three datasets, with improvements ranging from +0.055 (Refined Promise, Zero-shot) to +0.264 (Secreq, Zero-shot). The Llama-3-8B-Instruct model shows the largest absolute gains, particularly on Refined Promise where BT-APE improves upon Zero-shot by +0.296 and upon FewShot by +0.282. The Falcon3-7B-Instruct and Ministral-8B-Instruct-2410 models also exhibit consistent positive improvements over the classical baselines. When APE-PE2 is added to the comparison, the strongest-baseline picture changes: BT-APE matches or surpasses the best baseline (now including APE-PE2) in 6 of the 15 model–dataset configurations, while in the remaining nine the shortfall is consistently small, ranging from Δ = −0.005 (Falcon3-7B-Instruct against APE-PE2 on SecReq) to Δ = −0.038 (Granite-3.2-8B-Instruct against Few-shot on Refined Promise). Of these nine cases, five are narrow losses to APE-PE2 (margins between −0.005 and −0.013) and four are losses to classical baselines on the two tasks where they remain competitive (Refined J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
111:28
Zadenoori et al.
Promise for Falcon3-7B-Instruct and Granite-3.2-8B-Instruct; SecReq for Granite-3.2-8B-Instruct and Llama-3-8B-Instruct). The negative differences are negligible to small in magnitude and do not undermine the overall positive trend. Conclusion for RQ1. Based on the empirical evidence, we conclude that BT-APE significantly outperforms the four classical prompt-engineering approaches for requirements classification, while performing on par with the second automated prompt-optimization variant APE-PE2. Across 15 comparisons spanning three datasets, five LLMs, and four classical baseline strategies (Zero-shot, FewShot, COT, and CoT + Few-shot), BT-APE achieves higher 𝑤𝐹 1 scores with large effect sizes and statistical significance at 𝛼 = 0.05. Against APE-PE2, the difference is negligible and not statistically significant, suggesting that both automated prompt-engineering variants reach a comparable performance ceiling on these tasks. These findings establish BT-APE—together with APE-PE2—as a superior alternative to conventional prompting methods for the requirements-classification tasks discussed in this work. Positioning relative to PE2. While BT-APE outperforms classical baselines, its accuracy converges with PE2—its only direct competitor operating under identical budgets and protocols. BT-APE shows a negligible mean Δ of +0.001 in 𝑤𝐹 1 , no statistical significance, and a near-even win split (6 wins, 5 losses, 4 ties). Crucially, while BT-APE’s algorithmic modifications (bounded backtracking, balanced selection, and majority-voted F1) yield no accuracy gains here, they significantly lower the computational footprint. This lighter design makes the pipeline more computationally handleable for deployment on small servers, as demonstrated by the footprint analysis in the Appendix C. Key Findings for RQ1 • BT-APE significantly outperforms the four classical prompt-engineering approaches (Zero-shot, Few-shot, CoT, and CoT + Few-shot) for requirements classification. • Across 15 comparisons spanning three datasets and five LLMs, BT-APE achieves consistently higher 𝑤𝐹 1 scores than the classical baselines. • Improvements over the classical baselines show large effect sizes and statistical significance at 𝛼 = 0.05. • BT-APE performs on par with the optimization-based variant APE-PE2 (mean Δ = +0.001, negligible effect size, not statistically significant), indicating that both automated promptengineering methods reach a comparable performance ceiling. • Takeaway: BT-APE—together with APE-PE2—is a superior alternative to conventional prompting methods for requirements classification tasks. 5.3
Answers to RQ2: Factors Analysis to APE Performance
Analysis Approach. RQ2 examines whether the choice of dataset and LLM significantly affects BT-APE performance. The final results consist of one weighted-F1 (𝑤𝐹 1) value per (Dataset, LLM) combination, yielding a 3×5 design with 𝑛 = 15 observations. Before selecting a test, we assessed the normality assumption using the Shapiro–Wilk test on the 𝑤𝐹 1 values, which returned a borderline result (𝑊 = 0.898, 𝑝 = 0.088). Given the small sample and the marginal normality, we adopt distribution-free Friedman tests for the two main effects rather than relying on the normality assumption of parametric ANOVA. The Friedman test is well suited to a complete two-way layout with one observation per cell: it ranks performance within blocks and makes no distributional assumption. We test the dataset effect using LLMs as blocks, and the LLM effect using datasets as blocks, and report Kendall’s 𝑊 as the associated effect size. Because the design contains a single J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
BT-APE: A Computationally Light Backtracking Approach to Automatic Prompt Engineering for Requirements Classification
111:29
observation per cell, the Dataset × LLM interaction is not estimable and is therefore not tested; we instead examine it qualitatively from the cell-level results. Power Analysis. Before interpreting the hypothesis tests, we report a priori power estimates to contextualize the risk of Type II error, particularly for the LLM factor where the null hypothesis is not rejected. For the dataset effect (Friedman test with 𝑘 = 3 treatment levels and 𝑏 = 5 blocks), the observed effect size is Kendall’s 𝑊 = 1.00. Converting to the Friedman 𝜒 2 statistic via 𝜒 2 = 𝑏 · 𝑘 (𝑘 − 1) · 𝑊 = 5 × 3 × 2 × 1.00 = 30, and consulting a non-central 𝜒 2 distribution with 𝑑 𝑓 = 𝑘 − 1 = 2, the power to detect this effect at 𝛼 = 0.05 is effectively 1.00. The dataset effect is thus detected with certainty given the observed data. For the LLM effect (Friedman test with 𝑘 = 5 treatment levels and 𝑏 = 3 blocks), the situation is substantially more constrained. With only 𝑏 = 3 blocks (datasets), the Friedman test has limited ability to detect moderate LLM differences. We computed power via Monte Carlo simulation (10,000 replications) of the Friedman statistic under the alternative hypothesis for three target effect sizes, with 𝛼 = 0.05: Table 7. Simulated power of the Friedman test for the LLM effect (𝑘 = 5, 𝑏 = 3, 𝛼 = 0.05)
Target Kendall’s 𝑊 0.10 0.30 0.50 Observed (𝑊 = 0.24)
Effect interpretation
Estimated power
Small Moderate Large
0.07 0.22 0.51
Small–moderate
≈ 0.16
Note: Power was estimated by simulating 10,000 Friedman tests under each alternative, drawing rank matrices consistent with the target 𝑊 and the 𝑘 = 5, 𝑏 = 3 design. The observed 𝑊 = 0.24 falls between the small and moderate benchmarks.
The power estimates in Table 7 reveal a critical limitation: with only three blocks, the Friedman test achieves power of approximately 0.16 at the observed effect size (𝑊 = 0.24), and only 0.51 even for a large effect (𝑊 = 0.50). This means the test is substantially underpowered in this design, and the failure to reject the LLM null hypothesis must be interpreted with considerable caution. The observed result is consistent with two competing explanations: (a) LLM choice genuinely has a negligible effect under BT-APE, or (b) a moderate LLM effect exists but cannot be reliably detected with 𝑏 = 3 blocks. The data do not allow us to discriminate between these explanations. Crucially, the non-significant result should not be interpreted as evidence of equivalence across LLMs. Hypothesis Testing. With the above power context in mind, the dataset null hypothesis is rejected while the LLM null hypothesis is not, at the 𝛼 = 0.05 significance level, as summarized in Table 8. • Dataset Effect: There is a statistically significant difference in 𝑤𝐹 1 across datasets (Friedman 𝜒 2 (2) = 10.0, 𝑝 = 0.007), with a maximal effect size (Kendall’s 𝑊 = 1.00). The perfect concordance indicates that every LLM ranks the three datasets in the identical order. By median 𝑤𝐹 1, SecReq is the easiest task (𝑥˜ = 0.922), followed by PROMISE_NFR (𝑥˜ = 0.847), with PROMISE_Refined the hardest (𝑥˜ = 0.636). This ordering mirrors task complexity, from binary security classification to the fine-grained functional–quality distinction. Given the power of ≈ 1.00 at this effect size, this finding is robust. • LLM Effect: No statistically significant difference in 𝑤𝐹 1 was observed across LLMs (Friedman 𝜒 2 (4) = 2.92, 𝑝 = 0.572), with a small-to-moderate effect size (Kendall’s 𝑊 = 0.24). Median 𝑤𝐹 1 varies from Qwen2 (𝑥˜ = 0.852) down to Llama3 (𝑥˜ = 0.797), a numerical spread J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
111:30
Zadenoori et al.
of 0.055. However, as the power analysis shows, this test has only ≈ 16% power to detect an effect of the observed magnitude with 𝑏 = 3 blocks. The non-significant result is therefore inconclusive rather than confirmatory: it is compatible with a genuine absence of LLM-driven differences under BT-APE, but also with a moderate effect that the design lacks the power to detect. Replication with additional datasets (i.e., additional blocks) would be necessary to distinguish these interpretations. • Interaction Effect: With one observation per cell, the Dataset × LLM interaction is not estimable and is not tested. The cell-level results (Table 9) suggest possible taskdependent behaviour—for example, Ministral is competitive on SecReq (0.922) yet weakest on PROMISE_Refined (0.528), while Llama3 shows the opposite pattern (0.909 vs. 0.688)—but this pattern is not statistically confirmed and would require replicated measurements per cell to test formally. Table 8. Hypothesis Testing Results for RQ2
Effect
Statistic
p-value
Kendall’s 𝑊
Power†
Decision
H1
Dataset
𝜒 2 (2) = 10.0
0.007
1.00
≈ 1.00
H2
LLM
𝜒 2 (4) = 2.92
0.572
0.24
≈ 0.16
Reject H0 Fail to reject H0 (inconclusive)
Hyp.
† Power estimated at the observed Kendall’s 𝑊 via Monte Carlo simulation (10,000 replications); see Table 7. Note: Main
effects assessed with Friedman tests (dataset effect blocked on LLM; LLM effect blocked on dataset).
Best and Worst Configurations. The cell-level results, shown in Table 9, illustrate the possible task-dependent behaviour of the models. The best performances are concentrated on SecReq, led by Falcon3 (𝑤𝐹 1 = 0.947) and Qwen2 (𝑤𝐹 1 = 0.944). The worst performances are concentrated on PROMISE_Refined, with Ministral performing particularly poorly (𝑤𝐹 1 = 0.528). The withindataset spread for PROMISE_Refined (0.528–0.688, range = 0.160) is notably wider than for SecReq (0.858–0.947, range = 0.089), suggesting that model choice may matter more on harder tasks—a pattern that would warrant dedicated investigation with a replicated design. Table 9. Best and Worst Performing (Dataset, LLM) Combinations
Rank
(Dataset, LLM)
wF1
1 2 3 4 5
Top 5 SecReq + Falcon3 SecReq + Qwen2 SecReq + Ministral SecReq + Llama3 SecReq + Granite3
0.947 0.944 0.922 0.909 0.858
1 2 3 4 5
Bottom 5 PROMISE_Refined + Ministral PROMISE_Refined + Falcon3 PROMISE_Refined + Granite3 PROMISE_Refined + Qwen2 PROMISE_Refined + Llama3
0.528 0.606 0.636 0.648 0.688
J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
BT-APE: A Computationally Light Backtracking Approach to Automatic Prompt Engineering for Requirements Classification
111:31
Summary. Dataset choice has a large, statistically significant, and robustly detected effect on BT-APE performance, with perfect rank concordance across models (Kendall’s 𝑊 = 1.00) and a clear difficulty ordering (SecReq < PROMISE_NFR < PROMISE_Refined). For the LLM factor, the evidence is weaker and must be qualified: no statistically significant effect was found, but the Friedman test is substantially underpowered in a 𝑘 = 5, 𝑏 = 3 design, detecting only ≈ 16% of effects at the observed magnitude. The numerical performance spread across LLMs (median range: 0.055) and the wider within-dataset variance on the hardest task are descriptively consistent with a small-to-moderate LLM effect that the current design cannot confirm or rule out. Extending this analysis to additional RE classification datasets would be a necessary step before drawing firm conclusions about LLM-independence under BT-APE. Key Findings for RQ2 • Dataset choice has a large, robustly detected effect (Friedman 𝜒 2 (2) = 10.0, 𝑝 = 0.007; Kendall’s 𝑊 = 1.00, power ≈ 1.00): SecReq is easiest and PROMISE_Refined hardest, with every LLM agreeing on this ordering. • No statistically significant LLM effect was detected (Friedman 𝜒 2 (4) = 2.92, 𝑝 = 0.572; Kendall’s 𝑊 = 0.24), but this result is inconclusive: with only 𝑏 = 3 blocks, the test has ≈ 16% power at the observed effect size and cannot reliably distinguish absence of an effect from a moderate effect. • The Dataset × LLM interaction is not estimable with one observation per cell; celllevel patterns—particularly the wider LLM spread on PROMISE_Refined—hint at taskdependent behaviour but require replicated measurements to test. • Takeaway: Task difficulty is the dominant, well-supported driver of BT-APE performance. Whether LLM selection matters under BT-APE remains an open question that requires evaluation across a larger set of datasets before practitioners can safely deprioritize model choice. 5.4
Answers to RQ3: Prompt Features and Performance
Descriptive Statistics. Across BT-APE iterations, prompt features displayed consistent patterns of change. Prompts generally became more concise, with reductions in sentence count (SC) and word count (WC), while punctuation marker (PM) usage rose, reflecting a tendency toward more organized formatting. Lexical diversity (LD) declined progressively, pointing to a narrowing of vocabulary toward more task-relevant terms. Verb count (VB) increased moderately, suggesting a shift toward more directive phrasing. Syntactic complexity (SCx) showed a gradual downward trend, indicating that prompt structures became less elaborate over time. Ambiguity score (AS) remained broadly stable across iterations, while semantic drift (SD) varied considerably, spiking most noticeably during iterations involving major prompt reformulations. These descriptive trends are consistent across the 15 (dataset, LLM) trajectories, but the absolute levels of 𝑤𝐹 1 at which each trajectory operates differ substantially with task difficulty and model capability (cf. RQ2), motivating the mixed-effects analysis below. Statistical Test Results. We estimate a LMM with 𝑤𝐹 1 as the response, the eight prompt features as fixed effects, and a random intercept for each of the 15 (dataset, LLM) trajectories. This specification absorbs configuration-level baseline differences in 𝑤𝐹 1 into the random intercept, so that the fixed-effect coefficients 𝛽ˆ𝑘 estimate the within-trajectory association between each feature and performance. J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
111:32
Zadenoori et al.
The intra-class correlation coefficient is ICC = 0.683, indicating that approximately 68.3% of the residual variance in 𝑤𝐹 1 is attributable to between-trajectory differences rather than to withintrajectory variation in prompt features. This is the variance that the pooled OLS specification used in our preliminary analysis would have absorbed into a single inflated 𝑅 2 . Under the LMM, the 2 = 0.214 (variance explained by the fixed effects alone) and the conditional 𝑅 2 = 0.821 marginal 𝑅𝑚 𝑐 2 is the appropriate figure (variance explained by fixed and random effects jointly). The marginal 𝑅𝑚 for the prompt-feature claim and is, as expected, lower than the 0.761 obtained under naive pooling. The omnibus likelihood-ratio test against an intercept-only random-effects model is significant at 𝑝 < 0.001. Table 10. Linear mixed-effects model results for prompt features predicting 𝑤𝐹 1. Random intercepts are fitted for each (dataset, LLM) trajectory (𝐽 = 15). Fixed-effect coefficients are standardised; 𝑝-values are reported before Holm–Bonferroni correction across the eight features and the corrected significance is indicated in the rightmost column (∗: significant after correction; n.s.: not significant). Variable SC WC PM LD VB SCx AS SD 2 (fixed only) Marginal 𝑅𝑚 Conditional 𝑅𝑐2 (fixed + random) ICC (between-trajectory share) Number of trajectories ( 𝐽 ) Number of prompt observations (𝑁 )
Coef. (𝛽ˆ) −0.182 −0.149 0.193 −0.138 0.221 −0.124 −0.051 0.164
Std.Err. 0.038 0.042 0.034 0.036 0.035 0.035 0.038 0.033
t −4.79 −3.55 5.68 −3.83 6.31 −3.54 −1.34 4.97
p-value < 0.001 < 0.001 < 0.001 < 0.001 < 0.001 < 0.001 0.181 < 0.001 0.214 0.821 0.683 15 287
[0.025 −0.257 −0.231 0.126 −0.209 0.152 −0.193 −0.126 0.099
0.975] −0.107 −0.067 0.260 −0.067 0.290 −0.055 0.024 0.229
Sig. ∗ ∗ ∗ ∗ ∗ ∗ n.s. ∗
ˆ standard errors, 𝑡-statistics, 𝑝Table 10 presents the standardised fixed-effect coefficients (𝛽), values, and 95% confidence intervals for all eight predictors under the LMM. Sentence count (SC), word count (WC), lexical diversity (LD), and syntactic complexity (SCx) each exerted significant negative within-trajectory effects on performance. By contrast, punctuation markers (PM), verb count (VB), and semantic drift (SD) were associated with significant within-trajectory performance gains. Ambiguity score (AS) did not attain significance at 𝛼 = 0.05 after Holm–Bonferroni correction. Robustness Check on Terminal Prompts. To verify that the within-trajectory associations are not artefacts of the optimisation dynamics, we re-estimated the relationship on the terminal prompt 𝑝 ∗ of each trajectory (𝑛 = 15) using ordinary least squares; the transition feature 𝑆𝐷 is excluded here as it is undefined for a single prompt. The sign of every state-feature coefficient under the LMM is preserved on terminal prompts: VB and PM remain positive, while SC, WC, LD, and SCx remain negative. Statistical power at 𝑛 = 15 is limited, so several coefficients do not reach significance individually, but no sign reversal is observed. We therefore report VB, PM, SC, WC, LD, and SCx as robust correlates of effective prompts, and reserve a separate interpretation for SD below. Effect Sizes and Interpretation. Verb count (VB; 𝛽ˆ = 0.221, 𝑝 < .001) and punctuation markers (PM; 𝛽ˆ = 0.193, 𝑝 < .001) were the most influential positive state-feature predictors. These findings suggest that, within a given configuration, prompts built around action-oriented language and clear structural formatting tend to achieve stronger performance. On the negative side, both sentence count (SC; 𝛽ˆ = −0.182, 𝑝 < .001) and word count (WC; 𝛽ˆ = −0.149, 𝑝 < .001) were associated with lower performance, reinforcing the value of conciseness. Higher lexical diversity (LD; 𝛽ˆ = −0.138, 𝑝 < .001) also hurt performance, suggesting that a J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
BT-APE: A Computationally Light Backtracking Approach to Automatic Prompt Engineering for Requirements Classification
111:33
tighter, more focused vocabulary is preferable to a varied one. Greater syntactic complexity (SCx; 𝛽ˆ = −0.124, 𝑝 < .001) similarly reduced performance, pointing to the advantage of straightforward sentence structures. Ambiguity score (AS; 𝛽ˆ = −0.051, 𝑝 = 0.181) showed a negative trend but fell short of significance, implying that ambiguous phrasing may be somewhat harmful though its effect was inconsistent across iterations. Semantic drift (SD; 𝛽ˆ = 0.164, 𝑝 < .001) was a significant positive predictor under the LMM, but we interpret it separately from the state features. Because 𝑆𝐷 is by construction a property of consecutive prompts rather than of a prompt in isolation, its positive within-trajectory coefficient indicates that iterations involving larger semantic edits tend to coincide with higher 𝑤𝐹 1 — a characterisation of successful search dynamics rather than actionable guidance for designing a static prompt. The implication is that surface-level paraphrasing is unlikely to drive improvement; substantive semantic revision is what the optimiser exploits when it makes progress. Summary. Overall, the LMM analysis points to a clear profile for high-performing prompts: they are brief, action-driven (higher verb usage), and well-organised (greater punctuation use), with a tighter vocabulary and simpler syntactic structure. These six state-feature effects are robust: they are statistically significant under the LMM and their signs are preserved on terminal prompts. Semantic drift is associated with within-trajectory improvement but, because it describes a transition rather than a state, we describe it as a property of effective optimisation rather than as static2 = 0.214 indicates that the fixed-effect prompt features account prompt guidance. The marginal 𝑅𝑚 for a meaningful share of within-trajectory variance once between-configuration differences are absorbed by the random intercepts; the ICC of 0.683 confirms that a substantial portion of the variation in 𝑤𝐹 1 is configuration-driven (consistent with the dataset effect established in RQ2), which is precisely the variance that a pooled OLS would have misattributed to the prompt features themselves. Practitioners aiming to maximise 𝑤𝐹 1 should therefore focus on keeping prompts short and direct, using action verbs, maintaining clear formatting, and — when iterating — pursuing substantive semantic revision rather than surface-level paraphrasing. Key Findings for RQ3 • Under a linear mixed-effects model that controls for between-trajectory variance, higher verb count and increased punctuation markers were significantly associated with improved within-trajectory performance. • Prompts that were longer in sentence and word count, more lexically varied, or syntactically complex tended to perform worse on 𝑤𝐹 1. • Ambiguity showed a consistent negative trend but did not reach statistical significance after correction. • Semantic drift was a significant positive within-trajectory predictor, but is interpreted as a property of successful optimisation dynamics rather than as static-prompt design guidance. 2 = 0.214 of within-trajectory • The fixed-effect prompt features explained a marginal 𝑅𝑚 variance; an ICC of 0.683 indicates that a substantial share of overall variation in 𝑤𝐹 1 is driven by between-configuration differences absorbed by the random intercepts. • All state-feature signs were preserved under a terminal-prompt robustness check (𝑛 = 15). • Takeaway: Brief, action-oriented, and clearly structured prompts are robust correlates of strong outcomes; substantive semantic revision (rather than surface paraphrasing) characterises trajectories on which BT-APE makes progress. J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
111:34
5.5
Zadenoori et al.
Answers to RQ4: Class Definitions Initialization Impact
Results Analysis. Table 11 presents the weighted F1 scores (𝑤𝐹 1) for BT-APE-Informed and BT-APE-Uninformed across all five LLMs and three datasets. Across the 15 LLM-dataset pairs, BT-APE-Informed achieves numerically higher 𝑤𝐹 1 scores in 10 comparisons, while BT-APEUninformed performs better in 3 comparisons, with 2 ties. The mean improvement (Δ̄final ) across all pairs is +0.015, indicating a small average advantage for BT-APE-Informed. Table 11. Weighted F1 Scores for BT-APE-Informed vs. BT-APE-Uninformed Across LLMs and Datasets Dataset
BT-APE-Uninformed
BT-APE-Informed
Δfinal
Qwen/Qwen2-7B-Instruct tiiuae/Falcon3-7B-Instruct ibm-granite/granite-3.2-8b-instruct mistralai/Ministral-8B-Instruct-2410 meta-llama/Meta-Llama-3-8B-Instruct
Promise Refined Promise Refined Promise Refined Promise Refined Promise Refined
0.648 0.606 0.636 0.528 0.688
0.748 0.706 0.648 0.598 0.608
+0.100 +0.100 +0.012 +0.070 -0.080
Qwen/Qwen2-7B-Instruct tiiuae/Falcon3-7B-Instruct ibm-granite/granite-3.2-8b-instruct mistralai/Ministral-8B-Instruct-2410 meta-llama/Meta-Llama-3-8B-Instruct
Promise NFR Promise NFR Promise NFR Promise NFR Promise NFR
0.852 0.826 0.847 0.847 0.797
0.856 0.799 0.880 0.820 0.827
+0.004 -0.027 +0.033 -0.027 +0.030
Qwen/Qwen2-7B-Instruct tiiuae/Falcon3-7B-Instruct ibm-granite/granite-3.2-8b-instruct mistralai/Ministral-8B-Instruct-2410 meta-llama/Meta-Llama-3-8B-Instruct
SecReq SecReq SecReq SecReq SecReq
0.944 0.947 0.858 0.922 0.909
0.945 0.949 0.860 0.922 0.909
+0.001 +0.002 +0.002 0.000 0.000
LLM
Statistical Significance. Dimension 1: Final Performance Comparison. The Wilcoxon signed-rank test on Δfinal yields a rank sum of 𝑊 = 24 (sum of negative ranks; 𝑊 + = 67) with 𝑛 = 13 non-zero differences. Since the test statistic exceeds the critical value for a one-tailed test at 𝛼 = 0.05, we fail to reject the null hypothesis. The result is not statistically significant (𝑝 ≈ 0.15). The mean difference Δ̄final = +0.015 with a 95% confidence interval of [−0.012, 0.041]. The confidence interval crosses zero, consistent with the non-significant test result. According to our benchmarks, this effect size is considered negligible to small. Dimension 2: Improvement-over-Baseline Comparison. Table 12 presents the per-cell gains from baseline for both variants and the difference in gains (𝛿 gain = ΔInformed − ΔUninformed ). The gains are mixed: BT-APE-Informed shows larger gains in some LLM-dataset pairs (notably granite and Llama on Promise Refined, and Falcon and Ministral on Promise NFR), while BT-APE-Uninformed shows larger gains in others. The mean 𝛿 gain is +0.033 (95% CI: [−0.022, 0.088]), with the confidence interval crossing zero. A two-tailed Wilcoxon signed-rank test on 𝛿 gain yields 𝑊 = 49 (sum of negative ranks; 𝑊 + = 56) with 𝑛 = 14 non-zero differences. The result is not statistically significant (𝑝 ≈ 0.86). We therefore find no reliable difference between the two strategies in their relative improvement over their respective baselines. Summary. Contrary to our initial expectation, providing fine-grained, domain-grounded class definitions (BT-APE-Informed) did not yield a statistically significant improvement in final performance over starting from minimal, uninformed descriptions (BT-APE-Uninformed). The mean improvement of +0.015 in 𝑤𝐹 1 is small and not reliable across experimental conditions. The improvement-over-baseline analysis reinforces this conclusion: the difference in gains between the two strategies is also not statistically significant (𝛿 gain = +0.033, 𝑝 ≈ 0.86), with a confidence interval that crosses zero. Although BT-APE-Informed begins from a higher initial performance owing to domain knowledge, BT-APE-Uninformed’s iterative optimization closes most J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
BT-APE: A Computationally Light Backtracking Approach to Automatic Prompt Engineering for Requirements Classification
111:35
Table 12. Gains from Baseline for BT-APE-Informed and BT-APE-Uninformed
Dataset
ΔInformed
ΔUninformed
𝛿 gain
Qwen/Qwen2-7B-Instruct tiiuae/Falcon3-7B-Instruct ibm-granite/granite-3.2-8b-instruct mistralai/Ministral-8B-Instruct-2410 meta-llama/Meta-Llama-3-8B-Instruct
Promise Refined Promise Refined Promise Refined Promise Refined Promise Refined
+0.082 +0.093 +0.204 +0.093 +0.153
+0.155 +0.150 +0.012 +0.100 -0.080
-0.073 -0.057 +0.192 -0.007 +0.233
Qwen/Qwen2-7B-Instruct tiiuae/Falcon3-7B-Instruct ibm-granite/granite-3.2-8b-instruct mistralai/Ministral-8B-Instruct-2410 meta-llama/Meta-Llama-3-8B-Instruct
Promise NFR Promise NFR Promise NFR Promise NFR Promise NFR
+0.103 +0.118 +0.070 +0.126 +0.081
+0.108 -0.027 +0.136 -0.027 +0.030
-0.005 +0.145 -0.066 +0.153 +0.051
Qwen/Qwen2-7B-Instruct tiiuae/Falcon3-7B-Instruct ibm-granite/granite-3.2-8b-instruct mistralai/Ministral-8B-Instruct-2410 meta-llama/Meta-Llama-3-8B-Instruct
SecReq SecReq SecReq SecReq SecReq
+0.062 +0.064 -0.013 +0.076 +0.000
+0.065 +0.066 +0.050 +0.078 +0.000
-0.003 -0.002 -0.063 -0.002 0.000
LLM
of this gap, and the two strategies converge to comparable final performance. This demonstrates that BT-APE’s autonomous optimization is sufficiently robust to compensate for an uninformed starting point. Key Findings for RQ4 • Providing fine-grained, domain-grounded class definitions (BT-APE-Informed) did not yield statistically significant improvement in final performance over minimal, uninformed descriptions (BT-APE-Uninformed). • The mean final performance improvement of +0.015 in 𝑤𝐹 1 is negligible to small and not reliable across experimental conditions. • The relative improvement over baseline also showed no statistically significant difference between the two strategies (𝛿 gain = +0.033, 𝑝 ≈ 0.86). • BT-APE’s iterative optimization process is sufficiently robust to discover effective class definitions autonomously, achieving comparable final performance regardless of initialization strategy. • Takeaway: Domain knowledge in the initial seed is not necessary—BT-APE’s autonomous optimization compensates effectively, achieving comparable results whether initialized from informed or minimal class definitions. 6 6.1
Discussion Positioning relative to established results
To situate BT-APE relative to established results, we compare against two reference points: the supervised transfer-learning approach of Hey et al. (NoRBERT) [21], and the recent few-shot study of Binkhonain and Alfayez using large proprietary LLMs [8]. J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
111:36
Zadenoori et al.
Comparison protocol. The comparison is indicative rather than exact. NoRBERT reports unweighted per-class 𝐹 1 under 10-fold cross-validation for a fine-tuned model, whereas BT-APE reports weighted 𝐹 1 (𝑤𝐹 1 ) from a frozen LLM under a single 30/30/40 split. Numerical gaps must therefore be read as broad positioning signals rather than head-to-head measurements. Functional vs. non-functional classification (PROMISE NFR).. On the binary F/NFR task, BT-APE’s best configuration (𝑤𝐹 1 = 0.847, Qwen2-7B and Ministral-8B) remains below NoRBERT’s finetuned results, which reach per-class 𝐹 1 of roughly 0.90 for functional and 0.93 for non-functional requirements. This gap is expected: NoRBERT updates model parameters on labelled data, while BT-APE leaves the LLM weights frozen and optimises only the prompt. Against the few-shot LLM study of Binkhonain and Alfayez [8], BT-APE on F/NFR (𝑤𝐹 1 = 0.847) is competitive with the mid-range of proprietary models—GPT-4 and DeepSeek at 0.87–0.88—but trails the strongest configuration (Gemini-5FS at 0.92). Notably, BT-APE achieves this with 7–8B open-weight models rather than frontier-scale proprietary ones. Security classification (SecReq). The picture is more favourable on the security task. BT-APE reaches 𝑤𝐹 1 = 0.947 (Falcon3-7B) and 0.945 (Qwen2-7B), exceeding the best few-shot LLM results on Sec–NonSec (Gemini-5FS at 0.85, GPT4-5FS at 0.87) by a clear margin. Takeaway. Taken together, these comparisons indicate that BT-APE does not close the gap to fully fine-tuned supervised models such as NoRBERT on functional–non-functional classification, but it delivers strong—sometimes state-of-the-art—results on security classification while requiring no fine-tuning and using substantially smaller, openly available models. This positions BT-APE as a practical middle ground: it recovers much of the performance of heavyweight supervised or proprietary-LLM pipelines at a fraction of their training and deployment cost. The remaining gap on the hardest functional–quality distinctions is consistent with our finding (RQ2) that task complexity, rather than model choice, dominates performance. 7
Threats to Validity
We discuss potential threats to the validity of our study following the standard categorisation into construct, internal, external, and conclusion validity, and describe the measures taken to mitigate them. 7.1
Construct Validity
Construct validity concerns the degree to which our experimental setup captures the theoretical constructs we intend to measure. One threat lies in how we operationalise prompt quality. We use weighted 𝐹 1 (𝑤𝐹 1 ) as the primary performance metric, which is standard for requirements classification under class imbalance [4, 43]. However, 𝑤𝐹 1 does not capture every relevant dimension of prompt quality, such as output stability across runs, the interpretability of the generated labels, or computational efficiency. A second threat concerns our definition of effective prompts through linguistic features (e.g., verb count, punctuation markers, semantic drift). This feature set may not exhaust all theoretically relevant characteristics: properties such as instruction positioning or the use of in-prompt examples could also influence performance and are not modelled here. To mitigate the first threat, we report both weighted 𝐹 1 (Section 5) so that recall-oriented effects are visible alongside the balanced metric, and we complement aggregate performance with the prompt-feature analysis in RQ3, which examines lexical, syntactic, and semantic dimensions beyond the primary metric. To mitigate the second threat, the feature set was selected to cover three theoretically J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
BT-APE: A Computationally Light Backtracking Approach to Automatic Prompt Engineering for Requirements Classification
111:37
distinct families (lexical, syntactic, semantic) established in the prompt-engineering and linguisticprofiling literature [34, 42], and we explicitly separate state features from the transition feature (𝑆𝐷) to avoid conflating prompt properties with search dynamics. 7.2
Internal Validity
Internal validity refers to whether the observed effects can be attributed to the independent variables (prompting strategy, LLM choice, and dataset) rather than to confounding factors. A primary threat is the stochastic nature of LLM generation. Although we set the decoding temperature to 0 for deterministic outputs, some back-ends may still introduce non-determinism through request batching or hardware differences. We mitigated this by scoring every candidate with three-run majority voting and reporting the resulting 𝑤𝐹 1 , consistent with prior work on LLM evaluation stability. A second threat is potential data leakage: because the PROMISE and SecReq datasets are publicly available, an LLM may have encountered parts of them during pre-training. Crucially, since BT-APE iteratively rewrites prompts based on validation-set performance, any pre-existing familiarity would affect all conditions equally and therefore does not compromise the comparative conclusions between BT-APE and the baselines. A third threat concerns the interaction between the backtracking mechanism and random seed selection. We fixed random seeds across all conditions and verified, in a preliminary sensitivity analysis, that results remained stable across multiple seed values. A further consideration is the data partitioning strategy. To keep the evaluation signal constant across iterations and prompting strategies, we use a single fixed split rather than cross-validation, which would inject partition-to-partition noise into the 𝐹 1 comparisons that drive backtracking. Critically, we separate the data that drives optimisation from the data used to report performance: the dataset is partitioned into an example pool 𝐷 pool (30%), a validation set 𝐷 val (30%), and a held-out test set 𝐷 test (40%). Seed stability and the influence of 𝑋 and 𝑁 max on convergence are characterised in Appendix A; per-seed variance is an order of magnitude smaller than the reported effect sizes.All in-loop decisions of Algorithm 1—candidate scoring, ranking, the improvement check, and the backtracking trigger—are made exclusively on 𝐷 val , whereas 𝐷 test is consulted exactly once, to evaluate the final prompt 𝑝 ∗ . Because selection pressure is confined to 𝐷 val , the optimism that arises from retaining the best-scoring candidate is kept off the reported test figures, so the 𝐹 1 values in Section 5 are genuine held-out estimates rather than selection-inflated ones. Both BT-APE and all baselines are scored on the same 𝐷 test under the same three-run majority-voting protocol; baselines draw their in-context demonstrations (where applicable) from 𝐷 pool and perform no selection, so neither method enjoys an information advantage on the test set. We nonetheless acknowledge a residual limitation: BT-APE legitimately consumes labelled feedback from 𝐷 val during the search, whereas the baselines do not, and the single fixed split means our estimates are not averaged over partitions. The validation-to-test gap can be read directly from our results, since we report both the validation 𝐹 1 that the search optimises and the final test 𝐹 1 . Quantifying how this gap behaves under repeated splits, and under larger candidate budgets, would further strengthen the generalisation claims; we identify this as a priority for future work. To further characterise this threat, Appendix E reports a complementary leakage probe based on Jaccard similarity between LLM-generated requirement continuations and the ground-truth second halves of the original requirements. Across all five models and both publicly available datasets, the mean Jaccard similarity remains low (0.10–0.16), with no statistically significant difference between PROMISE and SecReq for any model. While this is not a proof of absence of memorisation, it provides converging evidence that the evaluated LLMs are not reproducing the dataset texts verbatim, supporting the validity of our comparative conclusions. J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
111:38
7.3
Zadenoori et al.
External Validity
External validity concerns the generalisability of our findings beyond the specific experimental setting. First, our evaluation uses three requirements datasets (SecReq, PROMISE NFR, and PROMISE Refined) and five LLMs in the 7B–8B parameter range. While these cover binary security classification, multi-class NFR classification, and a refined functional–quality distinction, the results may not generalise to other RE tasks such as requirements tracing, ambiguity detection, or completeness checking. Second, all evaluated LLMs are open-weight models in the 7B–8B range; the findings may not extend to larger proprietary models (e.g., GPT-4, Gemini Ultra) or to smaller models (1B–3B). However, our focus on accessible models aligns with practical RE scenarios in which cost and data-privacy considerations favour local deployment. Third, BT-APE’s performance may depend on the availability of a moderately sized labelled training set (we used 100–200 examples per dataset); practitioners with extremely limited labelled data (e.g., < 20 examples) may not observe comparable gains. To mitigate the generalisability threat, our evaluation spans three structurally distinct classification tasks (binary functional/non-functional, binary security, and four-class refined functional/quality) and five instruction-tuned LLMs from five different organisations, covering a range of attention mechanisms and pre-training corpora (Table 2). The released replication package [54] and the interactive tool (Appendix D) further support extension of the evaluation to additional datasets, larger or smaller models, and other RE classification tasks. 7.4
Conclusion Validity
Conclusion validity pertains to the statistical power and the appropriateness of the inferences drawn from the data. A primary threat is the risk of Type I errors arising from multiple comparisons across the 15 experimental conditions. We controlled this by applying the Holm–Bonferroni correction to all pairwise tests and by reporting effect sizes alongside 𝑝-values to distinguish statistical from practical significance: the rank-based effect size 𝑟 for the Wilcoxon signed-rank comparisons (RQ1, RQ4) and Kendall’s 𝑊 for the Friedman tests (RQ2). A second threat is the normality assumption underlying the linguistic-feature analysis in RQ3; where normality was violated, as confirmed by Shapiro–Wilk tests, we relied on non-parametric procedures. The explained variance (𝑅 2 ≈ 0.76) of the regression model should be interpreted as associative rather than causal, given the observational nature of the prompt-feature analysis. A further threat concerns the risk of Type II errors in our null findings, namely the absence of a statistically significant LLM effect in RQ2 and the absence of a statistically significant difference between BT-APE-Informed and BT-APE-Uninformed in RQ4. As detailed in Section 5.3, the Friedman test for the LLM factor operates on a 𝑘 = 5, 𝑏 = 3 design and achieves only approximately 16% power at the observed effect size (Kendall’s 𝑊 = 0.24), reaching 51% power even for a large effect (𝑊 = 0.50). The Wilcoxon signed-rank test used in RQ4 (𝑛 = 15 paired observations, 𝛼 = 0.05) is similarly limited in its ability to detect small effects. Both null outcomes are therefore consistent with two competing interpretations: a genuine absence of effect, or a true small-to-moderate effect that the present design lacks the statistical power to detect. The data do not allow us to discriminate between these interpretations, and the null findings should be read as observational rather than as evidence of equivalence. Replication with additional datasets (adding blocks to the Friedman design) and additional (dataset, LLM) pairs (increasing 𝑛 for the Wilcoxon test) would be required to resolve this ambiguity, and we identify both extensions as priorities for future work. 8
Conclusion
In this paper, we investigated whether APE techniques developed for general NLP benchmarks transfer to domain-specific requirements classification, and how alternative single-trajectory APE J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
BT-APE: A Computationally Light Backtracking Approach to Automatic Prompt Engineering for Requirements Classification
111:39
designs compare in this setting. Building on our preliminary work [55], we framed prompt design as an optimisation problem and instantiated two single-trajectory APE methods: PE2, which conditions each proposal on the top-𝑛 historical prompts with their validation scores, and BTAPE, our backtracking-based variant which conditions each proposal on the current prompt and a balanced four-example batch and uses bounded patience to control trajectory updates. Both methods share the same underlying paradigm—iterative LLM-proposed refinement conditioned on labelled feedback—but instantiate it through structurally different proposal mechanisms. We further studied the role of class definitions as a design variable by contrasting two initialisation strategies: BT-APE-Uninformed, which begins from minimal descriptions, and BT-APE-Informed, which is seeded with definitions curated from established RE literature and standards. We evaluated both APE methods alongside four classical prompting baselines (zero-shot, fewshot, chain-of-thought, and their combination) on three widely used benchmark datasets (PROMISE, PROMISE-Refined, and SecReq) and five instruction-tuned LLMs (Qwen2-7B, Falcon3-7B, Granite3.2-8B, Ministral-8B, and LLaMA-3-8B), enabling a controlled comparison across datasets, architectures, and prompting strategies. Our results yield five main findings.
(1) APE transfers to RE classification. Both BT-APE and PE2 deliver large, statistically significant accuracy gains over every classical prompting baseline across the 15 model–dataset configurations, with medium-to-large effect sizes and 𝑝 < 0.01 after Holm–Bonferroni correction. The transfer of APE from general NLP benchmarks to domain-specific RE classification is robust across datasets and model architectures. (2) Structurally different APE methods converge on accuracy. BT-APE and PE2 are statistically indistinguishable in final weighted F1 (Δ = +0.001, negligible effect size, Wilcoxon 𝑝 > 0.05), with cell-level wins split nearly evenly. The accuracy ceiling on these tasks appears paradigm-determined—driven by the underlying iterative, feedback-conditioned refinement scheme—rather than determined by the specific proposal mechanism. (3) The two methods occupy distinct points in an operational trade-off space. Although accuracy is equivalent, the methods differ structurally along three axes that we characterize empirically: per-iteration context size (PE2’s input grows with the prompt history; BT-APE’s is bounded), wall-clock cost (which follows from the context-size differential), and hyperparameter interpretability (BT-APE’s patience parameter 𝑋 exposes an explicit exploration–exploitation knob; PE2’s reactive top-1 re-selection does not). Practitioners can therefore select among APE methods on the basis of deployment constraints rather than expected accuracy. (4) Prompt-feature analysis identifies correlates of effective prompts. Effective prompts are concise, action-oriented (higher verb count), structurally clear (higher punctuation-marker count), and evolve through meaningful semantic refinements (higher semantic drift) rather than surface-level paraphrasing. These correlates offer actionable guidance for both manual prompt design and the steering of future automatic prompt-generation procedures. (5) Domain-informed initialisation does not provide a detectable advantage. BT-APEInformed and BT-APE-Uninformed converge to comparable final performance (Δ = +0.015 weighted F1, Wilcoxon 𝑝 ≈ 0.15). The iterative refinement is sufficiently robust to discover effective class definitions autonomously, lowering the barrier to adoption for practitioners without deep domain expertise. We note, however, that the design is underpowered to rule out a small genuine effect favoring informed initialization, and the result should be read as observational rather than as evidence of equivalence.
J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
111:40
Zadenoori et al.
To support reproducibility and further research, we release a publicly available replication package containing the prompts, datasets, optimization traces, and evaluation scripts used in this study [54]. Declaration on the Use of Generative AI Generative AI tools were used in a supporting role during this work to assist with (i) conceptualising approaches, (ii) identifying and correcting errors in the code, (iii) drafting and polishing prose in selected sections of the manuscript, and (iv) producing an initial version of Figure 1 (subsequently reviewed, refined, and validated step by step by Author 1 and Author 5). All generated suggestions were critically checked, validated, and rewritten by the authors, who bear sole responsibility for all results and content presented herein. References [1] 2018. ISO/IEC/IEEE International Standard - Systems and software engineering – Life cycle processes – Requirements engineering. ISO/IEC/IEEE 29148:2018(E) (2018), 1–104. doi:10.1109/IEEESTD.2018.8559686 [2] Waleed Abdeen, Michael Unterkalmsteiner, Krzysztof Wnuk, Alessio Ferrari, and Panagiota Chatzipetrou. 2025. Language models to support multi-label classification of industrial data. In 2025 IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER). IEEE, 45–55. [3] Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. 2023. Gpt-4 technical report. arXiv preprint arXiv:2303.08774 (2023). [4] Waad Alhoshan, Alessio Ferrari, and Liping Zhao. 2023. Zero-shot learning for requirements classification: An exploratory study. Information and Software Technology 159 (2023), 107202. [5] Tawfeeq Alsanoosy. 2025. Large Language Model for Requirements Classification: An Ensemble Approach. Procedia Computer Science 270 (2025), 3648–3657. doi:10.1016/j.procs.2025.09.490 29th International Conference on KnowledgeBased and Intelligent Information & Engineering Systems (KES 2025). [6] Chetan Arora and et al. 2024. Advancing Requirements Engineering Through Generative AI: Assessing the Role of LLMs. Springer Nature Switzerland, 129–148. [7] Sarmad Bashir, Muhammad Abbas, Alessio Ferrari, Mehrdad Saadatmand, and Pernilla Lindberg. 2023. Requirements classification for smart allocation: A case study in the railway industry. In 2023 IEEE 31st International Requirements Engineering Conference (RE). IEEE, 201–211. [8] Manal Binkhonain and Reem Alfayez. 2025. Are prompts all you need? Evaluating prompt-based Large Language Models (LLM)s for software requirements classification. Requir. Eng. 30, 4 (Sept. 2025), 423–443. doi:10.1007/s00766-025-00451-8 [9] Pierre Bourque and Richard E. Fairley (Eds.). 2024. Guide to the Software Engineering Body of Knowledge (SWEBOK) (version 4.0 ed.). IEEE Computer Society. https://www.computer.org/education/bodies-of-knowledge/softwareengineering/v4 Available online: https://www.computer.org/education/bodies-of-knowledge/software-engineering/v4. [10] Haowei Cheng, Jati H Husen, Yijun Lu, Teeradaj Racharak, Nobukazu Yoshioka, Naoyasu Ubayashi, and Hironori Washizaki. 2024. Generative ai for requirements engineering: A systematic literature review. arXiv preprint arXiv:2409.06741 (2024). [11] Flavio Chierichetti and Ravi Kumar. 2015. LSH-Preserving Functions and Their Applications. J. ACM 62, 5, Article 33 (Nov. 2015), 25 pages. doi:10.1145/2816813 [12] Jane Cleland-Huang, Sepideh Mazrouee, Huang Liguo, and Dan Port. 2007. NFR Dataset. doi:10.5281/zenodo.268542 [13] Jane Cleland-Huang, Raffaella Settimi, Xuchang Zou, and Peter Solc. 2007. Automated classification of non-functional requirements. Requirements engineering 12, 2 (2007), 103–120. [14] Fabiano Dalpiaz, Davide Dell’Anna, Fatma Basak Aydemir, and Sercan Çevikol. 2019. Requirements classification with interpretable machine learning and dependency parsing. In RE’19. IEEE, 142–152. [15] V. De Martino, M. A. Zadenoori, X. Franch, and A. Ferrari. 2025. Green Prompt Engineering: Investigating the Energy Impact of Prompt Design in Software Engineering. arXiv preprint arXiv:2509.22320 (2025). [16] Neil A. Ernst and John Mylopoulos. 2010. On the Perception of Software Quality Requirements during the Project Lifecycle. In Requirements Engineering: Foundation for Software Quality, Roel Wieringa and Anne Persson (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 143–157. [17] Alessio Ferrari, Sallam Abualhaija, and Chetan Arora. 2024. Model Generation with LLMs: From Requirements to UML Sequence Diagrams. In REW’24. IEEE, 291–300. [18] Alessio Ferrari, Felice Dell’Orletta, Andrea Esuli, Vincenzo Gervasi, Stefania Gnesi, et al. 2017. Natural language requirements processing: a 4D vision. IEEE Software 34, 6 (2017), 28–35. J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
BT-APE: A Computationally Light Backtracking Approach to Automatic Prompt Engineering for Requirements Classification
111:41
[19] Martin Glinz. 2007. On Non-Functional Requirements. In 15th IEEE International Requirements Engineering Conference (RE 2007). 21–26. doi:10.1109/RE.2007.45 [20] Charles Haley, Robin Laney, Jonathan Moffett, and Bashar Nuseibeh. 2008. Security Requirements Engineering: A Framework for Representation and Analysis. IEEE Trans. Softw. Eng. 34, 1 (Jan. 2008), 133–153. doi:10.1109/TSE.2007. 70754 [21] Tobias Hey, Jan Keim, Anne Koziolek, and Walter F Tichy. 2020. NoRBERT: Transfer learning for requirements classification. In RE’20. IEEE, 169–179. [22] Xinyi Hou, Yanjie Zhao, Yue Liu, Zhou Yang, Kailong Wang, Li Li, Xiapu Luo, David Lo, John Grundy, and Haoyu Wang. 2024. Large language models for software engineering: A systematic literature review. ACM Transactions on Software Engineering and Methodology 33, 8 (2024), 1–79. [23] Kaicheng Huang, Fanyu Wang, Yutan Huang, and Chetan Arora. 2025. Prompt Engineering for Requirements Engineering: A Literature Review and Roadmap. arXiv preprint arXiv:2507.07682 (2025). [24] Daan Kepel and Konstantina Valogianni. 2024. Autonomous Prompt Engineering in Large Language Models. arXiv:2407.11000 [cs.CL] https://arxiv.org/abs/2407.11000 [25] Barbara Kitchenham, Lech Madeyski, and David Budgen. 2022. SEGRESS: Software Engineering Guidelines for Reporting Secondary Studies. IEEE Transactions on Software Engineering 49, 3 (2022). [26] Eric Knauss, Siv Houmb, Kurt Schneider, Shareeful Islam, and Jan Jürjens. 2011. Supporting requirements engineers in recognising security issues. In Requirements Engineering: Foundation for Software Quality: 17th International Working Conference, (REFSQ 2011) (28-30). Springer, Essen, Germany, 4–18. [27] Eric Knauss, Siv Hilde Houmb, Shareeful Islam, Jan Jürjens, and Kurt Schneider. 2021. SecReq. doi:10.5281/zenodo. 4530183 [28] Armin Kobilica, Mohammed Ayub, and Jameleddine Hassine. 2020. Automated identification of security requirements: A machine learning approach. In Proceedings of the 24th International Conference on Evaluation and Assessment in Software Engineering. 475–480. [29] Zijad Kurtanović and Walid Maalej. 2017. Automatically classifying functional and non-functional requirements using supervised machine learning. In 2017 IEEE 25th International Requirements Engineering Conference (RE). IEEE, Lisbon, Portugal, 490–495. [30] Minchan Kwon, Gaeun Kim, Jongsuk Kim, Haeil Lee, and Junmo Kim. 2024. StablePrompt: Automatic Prompt Tuning using Reinforcement Learning for Large Language Models. arXiv preprint arXiv:2410.07652 (2024). [31] Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, Sebastian Riedel, and Douwe Kiela. 2020. Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks. Advances in Neural Information Processing Systems 33 (2020). [32] Manjeshwar Aniruddh Mallya, Alessio Ferrari, Mohammad Amin Zadenoori, and Jacek Dabrowski. 2026. From Online User Feedback to Requirements: Evaluating Large Language Models for Classification and Specification Tasks. In Requirements Engineering: Foundation for Software Quality - 32nd International Working Conference, REFSQ 2026, Poznań, Poland, March 23-26, 2026, Proceedings (Lecture Notes in Computer Science), Renata S. S. Guizzardi and João Araújo (Eds.). Springer, 161–177. doi:10.1007/978-3-032-21423-2_11 [33] M. A. Mallya, A. Ferrari, M. A. Zadenoori, and J. Dąbrowski. 2026. RITA: A Tool for Automated Requirements Classification and Specification from Online User Feedback. arXiv preprint arXiv:2601.11362 (2026). [34] Alessio Miaschi, Felice Dell’Orletta, and Giulia Venturi. 2024. Evaluating Large Language Models via Linguistic Profiling. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, Yaser Al-Onaizan, Mohit Bansal, and Yun-Nung Chen (Eds.). Association for Computational Linguistics, Miami, Florida, USA, 2835–2848. doi:10.18653/v1/2024.emnlp-main.166 [35] Thomas Olsson, Séverine Sentilles, and Efi Papatheocharous. 2022. A systematic literature review of empirical research on quality requirements. Requirements Engineering 27, 2 (June 2022), 249–271. doi:10.1007/s00766-022-00373-9 [36] Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Christiano, Jan Leike, and Ryan Lowe. 2022. Training language models to follow instructions with human feedback. arXiv:2203.02155 [cs.CL] https://arxiv.org/abs/2203.02155 [37] Jordan Peer, Yaniv Mordecai, and Yoram Reich. 2024. NLP4ReF: Requirements classification and forecasting: From model-based design to large language models. In 2024 IEEE Aerospace Conference. IEEE, 1–16. [38] Kai Petersen, Sairam Vakkalanka, and Ludwik Kuzniarz. 2015. Guidelines for Conducting Systematic Mapping Studies in Software Engineering: An Update. Information and Software Technology 64 (2015). [39] Reid Pryzant, Dan Iter, Jerry Li, Yin Tat Lee, Chenguang Zhu, and Michael Zeng. 2023. Automatic Prompt Optimization with "Gradient Descent" and Beam Search. arXiv:2305.03495 [cs.CL] https://arxiv.org/abs/2305.03495 [40] Yuman Qin and Rong Peng. 2025. ChatNRC: A Non-functional Requirement Classification Framework Based on a Generative and Discriminative Mechanism. In 2025 32nd Asia-Pacific Software Engineering Conference (APSEC). 467–478.
J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
111:42
Zadenoori et al.
doi:10.1109/APSEC66846.2025.00052 [41] Gokul Rejithkumar and Preethu Rose Anish. 2025. NICE: Non-Functional Requirements Identification, Classification, and Explanation Using Small Language Models. In 2025 IEEE/ACM 47th International Conference on Software Engineering: Software Engineering in Practice (ICSE-SEIP). 284–295. doi:10.1109/ICSE-SEIP66354.2025.00031 [42] Alberto D Rodriguez, Katherine R Dearstyne, and Jane Cleland-Huang. 2023. Prompts matter: Insights and strategies for prompt engineering in automated software traceability. In REW’23. IEEE, 455–464. [43] Sarah Santos, Travis D. Breaux, Thomas B. Norton, Sara Haghighi, and Sepideh Ghanavati. 2024. Requirements Satisfiability with In-Context Learning. In RE’24. IEEE, 168–179. [44] Md Shafikuzzaman, Md Rakibul Islam, Shuaib Zaman, Andrew Ma, and Anwarul Islam Sifat. 2025. On the Effectiveness of Zero-Shot and Few-Shot Pretrained Language Models for Software Requirement Classification. IEEE Access 13 (2025), 159439–159453. doi:10.1109/ACCESS.2025.3607813 [45] Guttorm Sindre and Andreas Opdahl. 2003. A Reuse-Based Approach to Determining Security Requirements. (05 2003). [46] Hamed Taherkhani, Melika Sepidband, Hung Viet Pham, Song Wang, and Hadi Hemmati. 2026. Automated Prompt Engineering for Cost-Effective Code Generation Using Evolutionary Algorithms. ACM Trans. Softw. Eng. Methodol. (March 2026). doi:10.1145/3805704 Just Accepted. [47] Maciej Tomczak and Ewa Tomczak-Łukaszewska. 2014. The need to report effect size estimates revisited. An overview of some recommended measures of effect size. 21 (01 2014), 19–25. [48] Jonathan Ullrich, Matthias Koch, and Andreas Vogelsang. 2025. From Requirements to Code: Understanding Developer Practices in LLM-Assisted Software Engineering. In 2025 IEEE 33rd International Requirements Engineering Conference (RE). 257–266. [49] Vasily Varenov and Aydar Gabdrahmanov. 2021. Security requirements classification into groups using nlp transformers. In 2021 IEEE 29th International Requirements Engineering Conference Workshops (REW). IEEE, Notre Dame, IN, USA, 444–450. [50] Andreas Vogelsang and Jannik Fischbach. 2024. Using Large Language Models for Natural Language Processing Tasks in Requirements Engineering: A Systematic Guideline. arXiv:2402.13823 [cs.SE] https://arxiv.org/abs/2402.13823 [51] Ruochen Wang, Sohyun An, Minhao Cheng, Tianyi Zhou, Sung Ju Hwang, and Cho-Jui Hsieh. 2024. One Prompt is not Enough: Automated Construction of a Mixture-of-Expert Prompts. arXiv:2407.00256 [cs.AI] https://arxiv.org/abs/ 2407.00256 [52] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed Chi, Quoc V. Le, and Denny Zhou. 2022. Chain-of-Thought Prompting Elicits Reasoning in Large Language Models. arXiv preprint arXiv:2201.11903 (2022). [53] Qinyuan Ye, Maxamed Axmed, Reid Pryzant, and Fereshte Khani. 2024. Prompt Engineering a Prompt Engineer. arXiv:2311.05661 [cs.CL] https://arxiv.org/abs/2311.05661 [54] Amin Zadenoori. 2026. aminzadenoori/Backtracking-enhanced-Automatic- Prompt-Engineering-APE-for-requirementsclassification.: APE Classification Tool— Backtracking-enhanced Automatic Prompt Engineering for Requirements Classification. doi:10.5281/zenodo.20438927 [55] {Mohammad Amin} Zadenoori, Liping Zhao, Waad Alhoshan, and Alessio Ferrari. 2025. Automatic Prompt Engineering: The Case of Requirements Classification. In Requirements Engineering: Foundation for Software Quality (REFSQ) (Lecture Notes in Computer Science, Vol. 15588). Springer Nature, United States, 217–225. [56] M. A. Zadenoori, V. De Martino, J. Dabrowski, X. Franch, and A. Ferrari. 2025. Does Model Size Matter? A Comparison of Small and Large Language Models for Requirements Classification. arXiv preprint arXiv:2510.21443 (2025). [57] Mohammad Amin Zadenoori, Jacek Dąbrowski, Waad Alhoshan, Liping Zhao, and Alessio Ferrari. 2025. Large Language Models (LLMs) for Requirements Engineering (RE): A Systematic Literature Review. arXiv:2509.11446 [cs.SE] https://arxiv.org/abs/2509.11446 [58] Liping Zhao, Waad Alhoshan, Alessio Ferrari, Keletso J Letsholo, Muideen A Ajagbe, Erol-Valeriu Chioasca, and Riza T Batista-Navarro. 2021. Natural language processing for requirements engineering: A systematic mapping study. ACM Computing Surveys (CSUR) 54, 3 (2021), 1–41. [59] Xin Zhou, Martin Weyssow, Ratnadira Widyasari, Ting Zhang, Junda He, Yunbo Lyu, Jianming Chang, Beiqi Zhang, Dan Huang, and David Lo. 2025. Lessleak-bench: A first investigation of data leakage in llms across 83 software engineering benchmarks. arXiv preprint arXiv:2502.06215 (2025). [60] Yongchao Zhou, Andrei Ioan Muresanu, Ziwen Han, Keiran Paster, Silviu Pitis, Harris Chan, and Jimmy Ba. 2023. Large Language Models Are Human-Level Prompt Engineers. arXiv:2211.01910 [cs.LG] https://arxiv.org/abs/2211.01910
J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
BT-APE: A Computationally Light Backtracking Approach to Automatic Prompt Engineering for Requirements Classification
A
111:43
Hyperparameter Sensitivity Analysis and Convergence Dynamics
The optimization trajectory of our backtracking variant depends on two parameters: the maximum iteration horizon (𝑁 max ) and the backtracking fail-patience threshold (𝑋 ). We report a smallscale sensitivity analysis on the PROMISE dataset using LLaMA-3-8B to characterize how these parameters shape the search behavior and to motivate the values used in the main experiments. We emphasize at the outset that this analysis is exploratory: five seeds per configuration cannot support strong claims of statistical superiority, and we use the results to describe qualitative regimes rather than to declare an optimal setting. A.0.1 Protocol. We varied the patience threshold 𝑋 ∈ {1, 3, 5} and the horizon 𝑁 max ∈ {20, 30}, yielding six configurations. Each configuration was run with 𝑆 = 5 random seeds, drawing independent splits and proposer samples. For each run we record the final test weighted F1 (𝑤𝐹 1) under the same 3-run majority-voting protocol used throughout the paper. We report the mean and standard deviation across seeds; given the small sample, all standard deviations should be read as rough indications of run-to-run spread rather than precise estimates. To summarize trajectory shape, we report two descriptive statistics computed on the per-iteration validation 𝑤𝐹 1 sequence of each run, then averaged across seeds: V=
1
𝑁 ∑︁ max −1
𝑁 max − 1
𝑡 =1
S=
|𝑤𝐹 1𝑡 +1 − 𝑤𝐹 1𝑡 | · I(𝑤𝐹 1𝑡 +1 < 𝑤𝐹 1𝑡 ),
𝑁 ∑︁ max −1
I(𝑤𝐹 1𝑡 +1 = 𝑤𝐹 1𝑡 ).
(3)
(4)
𝑡 =1
V captures the mean magnitude of downward movements (a proxy for how often and how sharply the search loses ground between iterations); S counts iterations in which validation 𝑤𝐹 1 is unchanged (a proxy for plateauing). These are descriptive summaries, not test statistics. Table 13. Final test 𝑤𝐹 1 and trajectory descriptives across five random seeds. Standard deviations are reported for completeness but should be interpreted with caution given 𝑆 = 5. 𝑋
𝑁
Final 𝑤𝐹 1 (𝜇 ± 𝜎 )
V
S
Observed trajectory pattern
1 1
20 30
0.782 ± 0.024 0.785 ± 0.029
0.084 0.091
2.1 2.4
Frequent downward moves, few plateaus Frequent downward moves, few plateaus
3 3
20 30
0.841 ± 0.006 0.842 ± 0.005
0.012 0.004
4.6 14.1
Low volatility, moderate plateauing Low volatility, extended plateauing
5 5
20 30
0.839 ± 0.009 0.844 ± 0.008
0.016 0.011
8.3 12.9
Low volatility, extended plateauing Low volatility, extended plateauing
A.0.2 Observed regimes. Three qualitative patterns emerge from Table 13. At 𝑋 = 1, the search exhibits substantially higher downward movement (V ≈ 0.08–0.09, roughly an order of magnitude above other settings) and noticeably lower final 𝑤𝐹 1 (mean ≈ 0.78). A plausible interpretation is that immediate backtracking after a single non-improving step is sensitive to evaluation noise: the search abandons trajectories that would have recovered. We do not claim this is the only explanation; it is consistent with the observed pattern but the sample is too small to rule out alternatives. At 𝑋 = 3 and 𝑋 = 5, mean final 𝑤𝐹 1 is similar (≈ 0.84 in all four cells), and the spread across seeds overlaps substantially. The two settings differ mainly in trajectory shape rather than endpoint: 𝑋 = 5 spends more iterations on plateaus (S roughly doubled at 𝑁 = 20) before recovering. J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
111:44
Zadenoori et al.
Extending the horizon to 𝑁 = 30 produces small numerical gains for all settings but inflates the plateau count. We use these observations qualitatively to motivate the default 𝑋 = 3, 𝑁 max = 20 used in the main experiments. We do not claim it is optimal; we claim it sits in a region where the search neither over-reacts to single non-improving steps (𝑋 = 1) nor commits long stretches of iteration to plateaus (𝑋 = 5, 𝑁 = 30). A.0.3 Resource profile. Table 14 reports cumulative input-context tokens and wall-clock optimization time per configuration. Larger 𝑋 and larger 𝑁 both increase resource use, as expected, since both extend the number of proposer calls the search makes before terminating. At fixed 𝑁 = 20, moving from 𝑋 = 3 to 𝑋 = 5 increases mean cumulative tokens by roughly 28% and mean wall-clock by roughly 37%; at 𝑁 = 30 the gap widens. These are deterministic consequences of the iteration count and are reported for practitioners who need to budget compute, not as evidence of a methodological advantage. Table 14. Resource use across hyperparameter configurations (5 seeds each). 𝑋
𝑁
Cumulative input tokens (𝜇 ± 𝜎 )
Wall-clock (min, 𝜇 ± 𝜎 )
1 1
20 30
8,400 ± 120 12,100 ± 180
5.4 ± 0.3 8.1 ± 0.4
3 3
20 30
12,650 ± 95 18,900 ± 115
8.5 ± 0.2 13.2 ± 0.5
5 5
20 30
16,200 ± 140 23,800 ± 210
11.6 ± 0.4 17.4 ± 0.7
A.0.4 Statistical comparisons and their limits. We complement the descriptive analysis with paired statistical tests across seeds. Because the same five seeds were used for each configuration, the appropriate test is the Wilcoxon signed-rank test on paired differences, not the rank-sum (Mann– Whitney) test. We use a two-sided 𝛼 = 0.05 and do not apply multiple-testing correction across the small number of comparisons reported here; the tests are exploratory. At 𝑁 = 20, the paired difference in final 𝑤𝐹 1 between 𝑋 = 3 and 𝑋 = 5 is not significant (Wilcoxon signed-rank, 𝑊 = 4, 𝑝 = 0.63, 𝑛 = 5). Extending to 𝑁 = 30 likewise does not produce a significant difference between 𝑋 = 3 and 𝑋 = 5 (𝑊 = 3, 𝑝 = 0.44). We stress that with 𝑛 = 5 paired observations, these tests have very limited power: the non-significant outcome is consistent with both genuine equivalence and a small-to-moderate true effect that the design cannot detect. We do not interpret these results as evidence of equivalence. For cumulative tokens at 𝑁 = 20, the paired difference between 𝑋 = 3 and 𝑋 = 5 is significant (𝑊 = 0, 𝑝 = 0.0079, 𝑛 = 5), with 𝑋 = 5 using approximately 28% more tokens on average. This is unsurprising and mechanically explained by the larger patience threshold permitting more non-improving iterations before backtracking; we report it for completeness rather than as a methodological finding. A.0.5 Summary. The sensitivity analysis supports a modest, practical claim: 𝑋 = 1 produces visibly more unstable trajectories and lower final 𝑤𝐹 1 in this setting, while 𝑋 = 3 and 𝑋 = 5 behave similarly on accuracy and differ mainly in resource use. We adopt 𝑋 = 3, 𝑁 max = 20 as the default for the main experiments because it sits in the lower-volatility regime at the lower end of the resource-use range observed here. We do not claim it is optimal across datasets, models, or task families; the small-sample, single-dataset, single-LLM nature of this analysis precludes such claims, and we identify a broader sensitivity study as future work. J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
BT-APE: A Computationally Light Backtracking Approach to Automatic Prompt Engineering for Requirements Classification
A.1
111:45
Data partitioning
Our aim is to characterize the behavior of the BT-APE procedure—how prompts are proposed, evaluated, ranked, and refined—across a controlled factorial grid of three datasets, five LLMs, and six prompting strategies. Because the LLM M is frozen, 𝐷 is not partitioned in the supervised sense. We perform a single random split into three disjoint subsets with fixed proportions: • Example pool 𝐷 pool (30%). Source of in-context demonstrations and optimization feedback. Each iteration samples balanced examples (one correctly classified positive, one correctly classified negative, one misclassified positive, one misclassified negative) to condition prompt proposal. Never used to score prompts. • Validation set 𝐷 val (30%). Used exclusively during the search to score each candidate (three-run majority voting), rank it in R, and drive the improvement check and backtracking trigger. All in-loop decisions of Algorithm 1 use 𝐷 val . • Test set 𝐷 test (40%). Held out, never consulted during optimization. Evaluated exactly once, on the final prompt 𝑝 ∗ , under the same three-run majority voting protocol. The separation of 𝐷 val from 𝐷 test is the central methodological safeguard: because BT-APE retains the best-scoring candidate and triggers backtracking on observed performance, scoring and reporting on the same subset would constitute selection against the evaluation data and bias the reported F1 optimistically. Confining in-loop selection to 𝐷 val and reserving 𝐷 test for a single terminal evaluation keeps this optimism off the reported test figures. The proportions balance the competing demands of the search: in-context learning needs only a handful of demonstrations per class, so 30% suffices for 𝐷 pool ; a further 30% keeps the variance of validation-F1 estimates low—which matters because backtracking compares F1 across iterations—while the remaining 40% yields a low-variance final test estimate. Why a single split rather than cross-validation. Standard 𝑘-fold cross-validation would in principle produce tighter confidence intervals on the reported test F1, and we acknowledge that as the textbook protocol. We use a single fixed split instead because of the computational cost of the experimental grid: three datasets × five LLMs × six prompting strategies = 90 cells, with each optimisation cell executing up to 𝑁 max = 20 iterations of three-run majority voting over 𝐷 val plus a classification pass over 𝐷 pool . A nested 𝑘-fold protocol would multiply the cost of every optimisation cell by 𝑘, pushing the total inference budget beyond what is feasible on the hardware used for this study (per-cell timings are reported in Appendix C). We chose to allocate the budget to breadth—more datasets, more LLMs, and a directly comparable BT-APE/PE2 baseline—rather than to repeated splits of a narrower grid. To bound the variance introduced by this choice, we run a multi-seed stability check on a representative cell and report the resulting per-seed standard deviation alongside the hyperparameter sensitivity analysis in Appendix A; the variance is an order of magnitude smaller than the effect sizes we report in Section 5, which gives us reasonable confidence that the headline comparisons are not artefacts of the particular split. Comparability across methods. Both BT-APE and all baselines are scored on the same held-out 𝐷 test , and the comparison in Section 5 is made exclusively there. Baselines draw their in-context demonstrations (where applicable) from 𝐷 pool and are evaluated under the same three-run majority voting protocol. BT-APE never sees 𝐷 test during the search and the baselines perform no selection, so neither method enjoys an information advantage on the reported figures. B
APE Baseline: PE2
To isolate the contribution of our three algorithmic departures from existing APEs methods, we implement PE2 [53] as our representative APE baseline. PE2 is the closest in spirit to our approach J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
111:46
Zadenoori et al.
Algorithm 2: PE2 Baseline (protocol-matched to Algorithm 1) Input: Dataset 𝐷, LLM M, initial prompt 𝑝 1 , max iters 𝑁 max = 20, history conditioning size 𝑛 = 3, error batch size 𝑘 = 4 Output: Best prompt 𝑝 ∗ , held-out test F1 // Phase 1: Initialization (identical splits to Algorithm 1) Split 𝐷 into 𝐷 pool (30%), 𝐷 val (30%), 𝐷 test (40%); 𝐹 ∗ ← 𝐹 val (𝑝 1 ) ; // 3-run majority voting on 𝐷 val 𝑝 ∗ ← 𝑝 1 , 𝑝 curr ← 𝑝 1 ; Insert (𝑝 1, 𝐹 ∗, 0) into history H ; // Phase 2: Iterative Refinement (history-aware, no patience) for 𝑡 = 1 to 𝑁 max do // Step 2.1: Build unconstrained error batch on 𝐷 pool Classify 𝐷 pool using 𝑝 curr (3-run voting); 𝐸 ← up to 𝑘 random misclassifications from 𝐷 pool ; // no class balancing // Step 2.2: Generate Candidate via PE2 meta-prompt Htop-𝑛 ← top-𝑛 entries of H by F1; 𝑝𝑡 ← Mproposal 𝑝 curr, Htop-𝑛 , 𝐸; 𝑝 meta ; // Step 2.3: Evaluate Candidate on 𝐷 val 𝐹 (𝑝𝑡 ) ← 𝐹 val (𝑝𝑡 ) ; // 3-run majority voting Insert (𝑝𝑡 , 𝐹 (𝑝𝑡 ), 𝑡) into H ; if 𝐹 (𝑝𝑡 ) ≥ 𝐹 ∗ then 𝑝 ∗ ← 𝑝𝑡 , 𝐹 ∗ ← 𝐹 (𝑝𝑡 ); // Step 2.4: Trajectory update — re-select top-1 from the full history 𝑝 curr ← arg max (𝑝,𝐹,·) ∈ H 𝐹 ; // no patience counter, no bounded back-tracking // Phase 3: Final held-out evaluation (test set touched once) return 𝑝 ∗ and 𝐹 test (𝑝 ∗ ) (Algorithm 1): both are single-trajectory, history-aware search procedures driven by errors observed on a held-out set, which makes PE2 the strongest available reference point for assessing whether our specific modifications—bounded back-tracking, balanced example batches, and majority- voted F1—yield concrete improvements. Algorithm 2 specifies the baseline as implemented in this work. Implementation details. The baseline is implemented in Python on top of the same LLM client used for Algorithm 1, with all hyper-parameters fixed to values that match our main method wherever the two algorithms share a notion of the parameter. Concretely, we use the same 30/30/40 pool/val/test split, the same deterministic seed for shuffling, the same 𝑁 max = 20 iterations, the same 3-run majority-voting evaluation on 𝐷 val , and the same single 3-run pass on 𝐷 test . The seed prompt 𝑝 1 given to PE2 is the seed prompt used by Algorithm 1, so the search starts from the same point in prompt space. PE2-specific hyper-parameters are set to 𝑛 = 3 historical prompts shown to the proposer and 𝑘 = 4 error examples per iteration; we chose 𝑘 = 4 so that the error batch has the same cardinality as our balanced batch 𝐸, and 𝑛 = 3 to match the patience parameter 𝑋 = 3 of our method, in both cases to remove cardinality as a confound. The meta-prompt follows the structure described by Ye et al. [53]: it states the binary-classification task, lists the top-𝑛 historical prompts together with their validation F1 scores, lists the error batch (input, gold label, prediction), and asks the proposer to emit a single revised prompt wrapped in delimiter tags for robust parsing. Differences from our method. Three behavioural differences distinguish Algorithm 2 from Algorithm 1, and each corresponds to one of the modifications we claim as a contribution. J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
BT-APE: A Computationally Light Backtracking Approach to Automatic Prompt Engineering for Requirements Classification
111:47
(i) Trajectory update. PE2 re-selects 𝑝 curr as the historical top-1 at every iteration (Step 2.4). It has no patience counter: a single underperforming proposal causes an immediate jump to the best-so-far prompt, and a sequence of underperforming proposals all start from the same point. Our method instead remains on the current trajectory until 𝑋 = 3 consecutive iterations fail to improve over 𝐹 ∗ and then back-tracks one step down a ranked list via an explicit pointer (Algorithm 1, Step 2.5), which both prevents premature abandonment of locally promising trajectories and prevents lingering in unproductive ones. (ii) Example selection. PE2’s error batch (Step 2.1) is sampled uniformly at random from the misclassifications on 𝐷 pool and provides no guarantee on class composition: in the presence of label imbalance or asymmetric error rates, the batch may contain errors of a single class or omit success signals entirely. Our method (Algorithm 1, Step 2.6) instead enforces a balanced four-tuple containing one correctly classified positive, one correctly classified negative, one misclassified positive, and one misclassified negative, which guarantees that the proposer simultaneously sees both classes and both success and failure signals at every iteration. (iii) Meta-prompt conditioning. PE2 additionally conditions each proposal on the top-𝑛 historical prompts with their F1 scores, exposing the proposer to the full quality landscape of the search so far. Our method conditions only on 𝑝 curr and the balanced batch, on the rationale that recovery from poor regions is handled structurally by the back-tracking mechanism rather than by in-context exposure to score history. This makes each individual proposal call cheaper in tokens and removes a potential source of bias toward prompts that resemble historical high scorers. All other aspects of the procedure—splits, voting, iteration budget, seed prompt, and final test-set protocol—are held fixed across the two algorithms, so any difference in final test F1 is attributable to these three changes. C
Computational Efficiency and Token Overhead Comparison
A central question raised by the accuracy convergence reported in Section 5 is whether BT-APE and PE2 differ along non-accuracy dimensions that matter at deployment. We therefore profile both frameworks on the same (dataset, LLM) configurations used in the main experiments, measure per-iteration and cumulative resource use under a controlled protocol, and test the resulting differences for statistical significance. C.1
Protocol
We profile every (dataset, LLM) combination , yielding 3 × 5 = 15 cells. Each cell is run with 𝑆 = 5 random seeds, drawing independent splits, proposer samples, and example batches. The same seed produces the same split for both methods, so the per-cell comparison is paired. Hyperparameters are held to the main-experiment values (𝑁 max = 20, 3-run majority voting on 𝐷 val , identical seed prompt 𝑝 1 , identical 30/30/40 partition). Hardware and inference stack are constant across all runs: a single NVIDIA H200 (142 GB) GPU, vLLM 0.6.x with deterministic sampling (temperature = 0), batch size 1, FP16 weights. Wall-clock measurements exclude model-load time. Token counts use each model’s native tokenizer; cross-LLM absolute comparisons are therefore not made, but per-cell paired differences (within an LLM) are unaffected. C.2
Aggregate efficiency results
Table 15 summarises the four primary efficiency metrics, aggregated over all 75 runs (15 cells × 5 seeds). We report mean and standard deviation for each method, the mean paired difference Δ̄ with its bootstrap 95% confidence interval (10,000 resamples, paired by (cell, seed)), the relative reduction, the test statistic and exact 𝑝-value from a one-sided paired Wilcoxon signed-rank test J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
111:48
Zadenoori et al.
on the 15 per-cell mean differences (𝐻 1 : PE2 > BT-APE), the Holm–Bonferroni-corrected 𝑝-value √ across the four metrics, and the rank-based effect size 𝑟 = 𝑍 / 𝑁 . Table 15. Aggregate efficiency metrics across 15 (dataset, LLM) cells × 5 seeds. One-sided paired Wilcoxon signed-rank test on the 15 per-cell mean differences, Holm–Bonferroni-corrected across the four metrics. Metric
PE2
Cum. input tokens Cum. output tokens Mean prop. lat. (s) Total wall-clock (min)
50,460 ± 2,977 5,620 ± 410 7.42 ± 0.51 25.78 ± 2.32
Δ̄ [95% CI]
BT-APE 13,860 ± 930 5,380 ± 350 2.93 ± 0.21 8.75 ± 0.67
36,600 [35,500; 37,700] 240 [ −130; 610] 4.49 [4.15; 4.83] 17.03 [16.21; 17.85]
Red. −72.5% −4.3% −60.5% −66.1%
𝑊
𝑝 adj
𝑟
120 38 120 66.1
< 10 −4
0.88 0.15 0.88 0.88
0.247 < 10 −4 < 10 −4
The three resource metrics governed by input-context size (cumulative input tokens, proposer latency, and wall-clock) show strictly positive paired differences in every one of the 15 cells and survive Holm–Bonferroni correction with large effect sizes (𝑟 = 0.88). The fourth metric, cumulative output tokens, shows no significant difference: the gap is attributable to PE2’s input growth, not to differences in the length of generated prompts. C.3
Per-cell measurements
Table 16 reports cumulative input tokens per cell (mean ± SD over 5 seeds). Within-cell relative standard deviation is small (≈ 3% for PE2, ≈ 2% for BT-APE), reflecting that token counts are driven primarily by the deterministic meta-prompt structure and the stable length of generated candidates. The paired difference Δ = 𝑇PE2 − 𝑇BT-APE is strictly positive in every cell. Table 16. Cumulative input tokens (mean ± SD, 𝑆 = 5 seeds) per (dataset, LLM) cell. Per-cell reduction is computed as Δ/𝑇PE2 .
C.4
Dataset
LLM
PE2
BT-APE
Δ
Red.
PROMISE-NFR PROMISE-NFR PROMISE-NFR PROMISE-NFR PROMISE-NFR
LLaMA-3-8B Qwen2-7B Falcon3-7B Granite-3.2-8B Ministral-8B
46,000 ± 1,180 49,200 ± 1,420 47,300 ± 1,310 51,400 ± 1,510 50,800 ± 1,440
12,650 ± 285 12,800 ± 295 13,100 ± 305 14,200 ± 340 14,500 ± 335
33,350 36,400 34,200 37,200 36,300
−72.5% −74.0% −72.3% −72.4% −71.5%
PROMISE-Refined PROMISE-Refined PROMISE-Refined PROMISE-Refined PROMISE-Refined
LLaMA-3-8B Qwen2-7B Falcon3-7B Granite-3.2-8B Ministral-8B
48,600 ± 1,310 52,300 ± 1,560 50,400 ± 1,420 54,800 ± 1,640 53,900 ± 1,560
13,400 ± 305 13,550 ± 315 13,900 ± 325 15,100 ± 365 15,400 ± 360
35,200 38,750 36,500 39,700 38,500
−72.4% −74.1% −72.4% −72.4% −71.4%
SecReq SecReq SecReq SecReq SecReq
LLaMA-3-8B Qwen2-7B Falcon3-7B Granite-3.2-8B Ministral-8B
47,400 ± 1,260 50,700 ± 1,510 48,800 ± 1,370 53,000 ± 1,580 52,300 ± 1,500
13,000 ± 295 13,200 ± 305 13,500 ± 315 14,650 ± 350 14,950 ± 345
34,400 37,500 35,300 38,350 37,350
−72.6% −74.0% −72.3% −72.4% −71.4%
Decomposition: input vs. output tokens
The architectural divergence between BT-APE and PE2 concerns the input side of the proposer call (PE2’s history-augmented meta-prompt). To verify that the cumulative-token gap is not artefactually driven by candidate-prompt length, we report output (generated) tokens separately. Mean output J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
BT-APE: A Computationally Light Backtracking Approach to Automatic Prompt Engineering for Requirements Classification
111:49
tokens per proposer call are 281 ± 22 for PE2 and 269 ± 18 for BT-APE; cumulative outputs over 20 iterations are 5,620 ± 410 and 5,380 ± 350, respectively. The paired Wilcoxon test on the 15 per-cell differences does not reject equality (𝑊 = 38, 𝑝 = 0.247, 𝑟 = 0.15). The cumulative-input gap of Section C.2 is therefore attributable to PE2’s input growth, not to PE2 producing longer prompts. C.5
PE2 hyperparameter sensitivity
The aggregate comparison fixes PE2’s history size at 𝑛 = 3 and error-batch size at 𝑘 = 4 to match BT-APE’s batch cardinality and patience parameter (Section B). Because PE2’s input cost depends on both parameters, we run a sensitivity sweep on three representative cells (PROMISE-NFR × LLaMA3-8B, PROMISE-Refined × Qwen2-7B, SecReq × Falcon3-7B) with 𝑛 ∈ {1, 3, 5} and 𝑘 ∈ {2, 4, 8}, 5 seeds each. Table 17. PE2 cumulative input tokens and final 𝑤 𝐹 1 under varied (𝑛, 𝑘), averaged over three representative cells (𝑆 = 5 seeds each). BT-APE is included for reference. The right-most column reports the paired Wilcoxon 𝑝-value for the 𝑤 𝐹 1 difference vs. BT-APE (𝑛 = 15 paired observations, two-sided). Method
(𝑛, 𝑘 )
Cum. input
Reduction vs. BT-APE
𝑤𝐹 1
𝑝 vs. BT-APE
PE2 PE2 PE2 PE2 PE2 PE2 PE2 PE2 PE2
(1, 2) (1, 4) (1, 8) (3, 2) (3, 4) (3, 8) (5, 2) (5, 4) (5, 8)
30,400 ± 920 33,200 ± 980 38,800 ± 1,120 46,200 ± 1,310 49,000 ± 1,420 54,600 ± 1,560 61,900 ± 1,750 64,800 ± 1,830 70,400 ± 1,990
+130% +151% +194% +250% +271% +314% +369% +391% +433%
0.755 ± 0.011 0.762 ± 0.010 0.768 ± 0.009 0.770 ± 0.009 0.773 ± 0.008 0.775 ± 0.008 0.772 ± 0.009 0.773 ± 0.008 0.775 ± 0.008
0.012 0.031 0.118 0.181 0.227 0.296 0.214 0.232 0.301
BT-APE
—
13,200 ± 305
—
0.778 ± 0.008
—
Two observations follow. First, across all nine (𝑛, 𝑘) settings, PE2’s cumulative input is strictly greater than BT-APE’s on every cell and every seed. The smallest PE2 footprint (𝑛 = 1, 𝑘 = 2) still consumes 130% more input tokens than BT-APE. PE2 therefore cannot recover BT-APE’s footprint by hyperparameter tuning without abandoning the history-conditioning mechanism that defines the method. Second, PE2’s accuracy degrades at the smallest (𝑛, 𝑘) settings: at (𝑛 = 1, 𝑘 = 2), the 𝑤 𝐹 1 gap to BT-APE is −0.023 and the paired Wilcoxon test rejects equality (𝑝 = 0.012). At (𝑛 ≥ 3, 𝑘 ≥ 4), the gap is negligible and non-significant, consistent with the convergence result in Section 5. The implication is that PE2’s competitive operating regime is precisely the one in which it incurs the ≥ 3× input-token cost reported in Table 15. C.6
Cost-normalised comparison
Because Section 5 establishes that BT-APE and PE2 reach statistically indistinguishable final 𝑤 𝐹 1 , the relevant practical question is how much resource each method consumes per unit of accuracy delivered. Table 18 reports two cost-normalised metrics, computed per cell and averaged: cumulative input tokens per percentage point of final 𝑤 𝐹 1 , and total wall-clock seconds per percentage point of final 𝑤 𝐹 1 . At equivalent accuracy, BT-APE delivers each percentage point of 𝑤 𝐹 1 at approximately 27% of PE2’s input-token cost and 34% of its wall-clock cost. J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
111:50
Zadenoori et al.
Table 18. Cost-normalised efficiency: resource consumed per percentage point of final 𝑤 𝐹 1 , aggregated over 75 runs.
C.7
Metric
PE2
BT-APE
Ratio
BT-APE share
Input tokens per pp 𝑤𝐹 1 Wall-clock seconds per pp 𝑤𝐹 1
657 20.13
180 6.83
3.65× 2.95×
27.4% 33.9%
Scaling behaviour
The cumulative-cost ratio reported above is computed at the fixed iteration budget 𝑁 max = 20 used in the main experiments. Per iteration, PE2’s input grows approximately linearly: a linear fit over the 20 iterations of all 75 runs yields slope 152.7 ± 8.4 tokens/iteration (mean ± SD across cells, 𝑅 2 = 0.94 within-cell). BT-APE’s per-iteration input shows no detectable trend (Mann–Kendall, 𝜏 = −0.04, 𝑝 = 0.62); its cumulative grows linearly in 𝑁 max at the constant per-iteration rate. Extrapolating to 𝑁 max = 50, PE2 would consume approximately 2.3 × 105 cumulative input tokens against BT-APE’s 3.3 × 104 — a ratio that widens from 3.65× at 𝑁 max = 20 to approximately 7.0× at 𝑁 max = 50. We mark this as an extrapolation under the assumption that the linear growth observed within the measured range persists; the empirical claim is restricted to 𝑁 max = 20. C.8
Honest scoping of the claim
Two qualifications are necessary. First, part of the efficiency gap is a structural consequence of the two designs: PE2’s input context grows by construction with the prompt history, while BT-APE’s is bounded. The empirical contribution of this section is therefore not the existence of a gap but its magnitude under realistic optimisation budgets, its consistency across datasets and models, and the fact that it is not recoverable by tuning PE2’s (𝑛, 𝑘) within the design’s competitive operating range (Section C.5). Second, the absolute token counts (a few thousand per iteration for PE2) are well below the context windows of all five evaluated LLMs (8k–32k tokens), so at 𝑁 max = 20 the gap is primarily a cost and latency consideration rather than a feasibility limit. At longer horizons or with larger 𝑛, PE2’s input growth approaches hard context-window limits and the gap transitions from a cost concern to a structural constraint (Section C.7). C.9
Threats
Hardware specificity. Wall-clock measurements are tied to the H200 + vLLM configuration; latency ratios may differ on CPU-only inference, on quantised models, or under different batching strategies. We report token counts as the more transferable measure. Tokeniser differences. Each model uses its native tokeniser; absolute token counts are not directly comparable across LLMs. Per-cell paired comparisons (within an LLM) are unaffected, and all aggregate tests use within-cell paired differences. Iteration-budget choice. Measurements use 𝑁 max = 20. Section C.7 reports linear-fit extrapolation to larger budgets; the empirical claim is restricted to the measured range. D
An Interactive Tool for Prompt Optimization
To make our procedure reusable beyond the experiments reported in this work, we implemented an interactive tool3 that operationalizes the full pipeline—the prompting baselines, the backtrackingenhanced BT-APE loop of Algorithm 1, and per-class evaluation—behind a graphical interface. 3 The tool’s interface is built with Gradio https://www.gradio.app; dataset handling and metric computation use pandas https: //pandas.pydata.org and scikit-learn https://scikit-learn.org; model inference is issued through the requests HTTP client https: //requests.readthedocs.io to an Ollama https://ollama.com (or OpenAI-compatible) backend.
J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
BT-APE: A Computationally Light Backtracking Approach to Automatic Prompt Engineering for Requirements Classification
111:51
The tool requires no coding, infers the label set directly from the data, and is decoupled from any specific model provider: the same workflow runs against a locally hosted open-weight model (e.g., via Ollama) or any OpenAI-compatible endpoint. It thus serves three purposes: replicating our results, transferring the method to any single-label text-classification task, and exposing prompt optimization as an observable, step-by-step process. The interface follows the natural order of an experiment in five steps. In Data & Config (Fig. 3) the user uploads a CSV whose first column is the text and last column the ground truth; the tool reports the class distribution, lets the user pick the backend and model, and exposes the run hyperparameters—train/test split, majority-voting runs, the iteration budget 𝑁 max , and the backtracking threshold 𝑋 —as sliders. In Prompt (Fig. 4) the prompt is split into a fixed part that frames the task and fixes the output format, and an optimizable part holding the label definitions; only the latter is rewritten during optimization, focusing the search on the semantically meaningful portion of the prompt. Baselines (Fig. 6a) runs zero-shot, few-shot, Chain-of-Thought (CoT), and CoT + few-shot individually or together, reporting per-class F1 for each. The BT-APE Optimisation step (Fig. 5) is the core of the tool. It can advance one interactive iteration at a time or run automatically to the budget. At each iteration the engine meta-prompts the model to improve the optimizable section, evaluates the candidate on the test split with majority voting, ranks it by F1 , and—after 𝑋 consecutive non-improving steps—backtracks to the next-best prompt. The iteration log, the colored iteration-history strip (green = improvement, amber = backtrack), the live “best prompt” and its evolving optimizable section, and the current per-class metrics are all surfaced together, rendering the previously unclear dynamics of the search clearly visible. Finally, Results (Fig. 6b) contrasts every method run in the session by macro- and per-class F1 , making the gain of the optimized prompt over the strongest baseline immediately legible. The tool, together with the datasets and label definitions used in this paper, is available at replication package of the work [54]. E
Data Leakage Detection in LLMs.
In the context of requirements classification, data leakage refers to the risk that an LLM has seen parts of the evaluation data during its pre-training, potentially biasing results. A review of the current literature reveals that there is no peer-reviewed paper that systematically addresses this issue. To date, only Zhou et al.[59] has directly investigated data leakage considering that what they have studied different task than the text classification. However, a critical limitation of that work is that the authors assumed prior access to the LLM’s pre-training data, a condition we cannot satisfy. Consequently, we must follow only their core research question, which employed an automated way to study the leakage just based on the behavior of the LLMs. Their experimental results indicate that detecting data leakage using an automated metric like Perplexity is challenging, with accuracy ranging from only 40% to 50% in most cases. They encourage the research community to explore more effective automated methods for identifying data leakage, especially in scenarios where the model’s pre-training data is unknown. Given this gap, we propose our own approach to study leakage. Specifically, we follow an automated methodology, for measuring similarity between the LLM’s guess and the ground truth, we employ recent similarity metrics such as Jaccard similarity. To evaluate the model’s ability to generate requirement continuations, we first split each requirement into two halves and discard the second half. Let 𝑛 be the number of words removed during this trimming step. We then prompt the LLM with the preserved prefix and explicitly instruct it to continue the requirement using approximately 𝑛 words. This programmatic constraint ensures that the generated continuation is comparable in length to the original missing segment, allowing us to assess not only semantic J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
111:52
Zadenoori et al.
1 · Data & Config 2 · Prompt
3 · Baselines
4 · APE Optimisation
5 · Results
DATASET
⬆
Upload CSV — text column first, label column last
✓ 16 samples · 5 classes · train 5 · test Performance (4) Security (4)
Functional (3)
11
Scalability (3)
Availability (2)
LLM BACKEND
Backend ollama openai-compat
Base URL http://localhost:11434
Model llama3:8b-instruct
API key ••••••••
⌄
↻ Fetch models
RUN SETTINGS
30 1 8 3
Train split % Voting runs APE max iterations Backtrack threshold X
Fig. 3. Data & Config. The dataset is uploaded as a CSV (text first, label last); the tool infers the classes and their distribution, selects the backend and model, and exposes the run hyper-parameters as sliders.
1 · Data & Config
2 · Prompt
Fixed prompt (never changes) You are a precise text classifier. Classify text into exactly one of the provided categories. Output only the exact label name.
3 · Baselines
4 · APE Optimisation
5 · Results
Optimisable prompt (APE rewrites this) Performance: speed, latency, throughput. Security: authentication, encryption. Functional: user-visible features. Scalability: load, concurrent users. Availability: uptime, reliability.
Fig. 4. Prompt. The prompt is separated into a fixed task-framing part and an optimizable definitions part (highlighted); BT-APE rewrites only the latter.
coherence but also the model’s ability to reproduce realistic requirement granularity. The results of this analysis will be reported accordingly. The Jaccard similarity coefficient[11], often denoted as 𝐽 (𝐴, 𝐵), is a statistic used for comparing the similarity and diversity of sample sets. Defined as the size of the intersection of two sets divided by the size of their union, it quantifies the proportion of shared elements relative to the total distinct elements present in either set. Formally, for two sets 𝐴 and 𝐵, the Jaccard similarity is calculated as | 𝐽 (𝐴, 𝐵) = |𝐴∩𝐵 |𝐴∪𝐵 | , where the result ranges from 0 (indicating no common elements) to 1 (indicating that the two sets are identical). This metric is widely used in fields such as data mining, ecology, J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
BT-APE: A Computationally Light Backtracking Approach to Automatic Prompt Engineering for Requirements Classification
1 · Data & Config
2 · Prompt
3 · Baselines
Best prompt so far
Iteration log APE initialised. F1: 61.8% Iteration 1/8 — best: 61.8% ↑ Improved: 61.8% → 67.3% Iteration 2/8 — best: 67.3% → 64.1% (best: 67.3%) Iteration 3/8 — best: 67.3% → 65.0% (best: 67.3%) ↩ Backtrack → rank-2 prompt Iteration 4/8 — best: 67.3% ↑ Improved: 67.3% → 72.1%
You are a precise text classifier… Performance: requirements specifying measurable speed or latency thresholds…
(evolves) Current optimisable section Performance: requirements with explicit numeric thresholds for speed, latency, or throughput. Security: access control…
Iteration history
67%
4 · APE Optimisation 5 · Results
② Next iteration Run all automatically
① Init APE
#1
111:53
#2
#3
64%
improved
↩
Latest metrics — iteration 4 #4
72%
82% 76% 65% 70% 68%
Performance Security Functional Scalability Availability
#5
70%
backtrack
Fig. 5. BT-APE Optimisation. Interactive or automatic execution of Algorithm 1. The iteration log and colored history strip (green = improvement, amber = backtrack), the live best prompt and its evolving optimizable section, and the per-class metrics are shown together, exposing the optimization trajectory. 1 · Data & Config
2 · Prompt
3 · Baselines
4 · APE Optimisation
5 · Results 1 · Data & Config
Strategy zero_shot few_shot cot cot_few_shot
Run selected strategy Run all 4 baselines
2 · Prompt
3 · Baselines
4 · APE Optimisation
5 · Results
Status Refresh table
✓ Zero-shot — Macro F1: 54.2% ✓ Few-shot — Macro F1: 61.8% ▶ Running Chain-of-Thought…
Results — few-shot Performance Security Functional Scalability Availability
(a) Baselines: per-class F1 per strategy.
75% 68% 55% 60% 50%
Method
Macro F1
Perf.
Sec.
Func.
Scale
Avail.
Zero-shot
54.2%
42%
58%
51%
60%
60%
Few-shot
61.8%
67%
72%
55%
60%
55%
CoT
63.4%
70%
71%
58%
58%
60%
CoT + Few-shot 66.1%
74%
75%
62%
62%
57%
72.1%
82%
76%
65%
70%
68%
APE Optimized
(b) Results: weighted/per-class F1 across methods.
Fig. 6. Baselines and Results. (a) Each prompting strategy is run and scored per class. (b) The session summary contrasts the baselines with the BT-APE-optimized prompt; the optimized prompt yields the highest macro F1 and improves the weakest classes.
and natural language processing, particularly for binary attribute comparison and for measuring the overlap in cluster analysis or document tokenization. As reported in Figure 7 plots, all observed Jaccard similarities between the predicted trimmed part and the actual trimmed part of the sentence are relatively low. The overall mean scores across all requirements texts range from 0.1048 (Qwen2-7B) to 0.1648 (Ministral-8B), with other models falling in between (Falcon3-7B: 0.1404, Granite-8B: 0.1314, Llama-3-8B: 0.1245). Looking at percentile distributions, most values lie between approximately 0.05 (10th percentile) and 0.25 (90th percentile), depending on the model. For instance, Ministral-8B reaches a 90th percentile of 0.3197 overall, while Qwen2-7B’s 90th percentile is only 0.1779. When comparing datasets, the J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
111:54
Zadenoori et al.
Fig. 7. Jaccard similarity scores across different models and datasets. Higher values would indicate greater overlap.
mean Jaccard scores on Promise (range: 0.1051–0.1695) and SecReq (range: 0.1046–0.1600) are very similar, and t-tests confirm no statistically significant difference between the two datasets for any model (all p-values > 0.17). However, an ANOVA test does indicate significant differences across models (p = 0.0038), suggesting that some models (e.g., Ministral-8B, Falcon3-7B) tend to produce slightly higher token overlap than others; given that the residuals follow a normal distribution, the use of ANOVA and T-test are justified. While these numbers suggest that the models do not strongly reproduce the trimmed second half ground truth — given that Jaccard similarity well below 0.5 indicates limited overlap — we refrain from drawing firm conclusions about the presence or absence of data leakage based solely on this analysis. Several factors could influence these scores, including differences in model output length, tokenization, and inherent generation variability, none of which directly confirm memorization of training data. A more systematic investigation is required to properly separate genuine leakage from other confounding factors. Therefore, we leave a thorough study of data leakage in this context as an item for future work. F
Prompts and Definitions
This appendix documents the full set of prompts and class definitions used in our classification experiments, so that the results can be reproduced exactly. We first present the prompt structure: the system prompt that fixes the output format, followed by the four prompting strategies we compare—zero-shot, few-shot, chain-of-thought (CoT), and chain-of-thought with examples— and the automatic prompt-engineering prompt used to refine the class definitions. The prompt templates are written generically: the placeholder {classes} is substituted at run time with the list of candidate class labels for the classification task at hand, {class} with a single class label, and {Definitions}, {examples}, and {text} with the corresponding class definitions, in-context J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
BT-APE: A Computationally Light Backtracking Approach to Automatic Prompt Engineering for Requirements Classification
111:55
examples (few-shot settings only), and the requirement to be classified. We then list the class definitions that are inserted into the {Definitions} placeholder. F.1
System Prompt
As an expert system for classifying software requirements, your task is to carefully analyze each given requirement and assign it to exactly one of the following classes: {classes} Output only the label of the class that corresponds to the appropriate class. Do not provide any additional text, definitions, or justification. F.2
Classification Prompts
F.2.1
Zero-Shot Prompt (No Examples, No CoT).
Definitions: {Definitions} Requirement: {text} Using the Definitions above, classify the requirement and provide the final label in the format: "Label: {class}". F.2.2
Few-Shot Prompt (With Examples, No CoT).
Definitions: {Definitions} Examples: {examples} Requirement: {text} Using the Definitions and Examples above, classify the requirement and provide the final label in the format: "Label: {class}". F.2.3
Chain-of-Thought (CoT) Prompt (No Examples, With CoT).
Let’s analyze the classification step by step. Step 1: Understand the Definitions: {Definitions} Step 2: Apply this understanding to classify the following requirement: Requirement: {text} Step 3: Provide the final label in the format: "Label: {class}". F.2.4
Chain-of-Thought with Examples Prompt (With Examples, With CoT).
Let’s analyze the classification step by step. Step 1: Understand the Definitions: {Definitions} Step 2: Review the Examples: {examples} Step 3: Apply this understanding to classify the following requirement: Requirement: {text} Step 4: Provide the final label in the format: "Label: {class}". J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
111:56
F.3
Zadenoori et al.
APE Prompt
Role: You are a highly capable, thoughtful, and precise prompt engineer specializing in requirements classification. Background: A LLM has previously used a set of {Definitions} to automatically classify requirements into the candidate classes {classes}. Based on these definitions, it correctly classified some requirements but misclassified other requirements. Task: Your task is to enhance the {Definitions} of the classes {classes} to improve the classification accuracy of the large language model. You are given example results in the form [requirement text; true class; predicted class] to guide you in enhancing the definitions. • A set of example requirements that were correctly classified based on the definitions: {correctly_classified} • A set of example requirements that were incorrectly classified based on the definitions: {misclassified} You may add content, shorten, or rephrase the definitions to improve clarity and accuracy. Let’s think step by step: (1) Study the Definitions: Understand the provided definitions of the classes. (2) Analyse Examples: Analyze correctly classified and misclassified examples. (3) Success analysis: For each correctly classified example identify why the original definitions were successful. Ask yourself: Do certain words/phrases consistently lead to correct classification? Which parts of the definitions are clear, complete, and unambiguous? (4) Error analysis: For each misclassified example identify why the original definitions failed. Ask yourself: Do certain words/phrases consistently mislead? Are the definitions ambiguous, incomplete, or overlapping? (5) Enhance Definitions: Enhance the definitions by adding, reducing, or rephrasing content. (6) Enhancement Procedure: For problematic classes: (a) Add discriminative features: Incorporate missing characteristics from misclassified examples. (b) Create exclusion clauses: Explicitly state what doesn’t qualify (“This class excludes. . . ”). (c) Use comparative framing: Highlight differences between easily confused classes. (d) Simplify if needed: Simplify definitions when they appear to be too complex. (e) Rephrase if needed: Rephrase definitions when the phrasing or terminology is misleading. (7) Validation Constraints: (a) Ensure misclassification prevention: The revised definitions must theoretically prevent the same errors from recurring. (b) Avoid overfitting: Definitions should maintain generalizability through clear principles rather than example-specific fixes. Output the enhanced {Definitions} only, with no additional text. F.4
Class Definitions
These are the definitions inserted into the {Definitions} placeholder of the prompts above. Security Requirements. Security requirements are prescriptive constraints imposed on a system’s functional behaviour to operationalise its security goals. They are not functional requirements J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
BT-APE: A Computationally Light Backtracking Approach to Automatic Prompt Engineering for Requirements Classification
111:57
themselves but restrict how functions are performed in order to prevent, detect, or recover from harm, and are expressed in precise, operational terms that are clear enough for implementation by system designers and architects. Security requirements are derived from business and functional goals and may be categorised as primary—those derived directly from business and functional goals, whose satisfaction ensures the system meets its fundamental security objectives—or secondary—those that support the implementation of primary requirements (e.g. through detection or recovery) when direct enforcement is infeasible or too costly. They are manifestations of high-level organisational policies into the detailed requirements of a specific system and are deeply tied to the broader system context, which may extend beyond software to include other components or processes. Security requirements specify the system’s security policies and must address risks, threats, and assets, while influencing and being influenced by security mechanisms, vulnerabilities, and attacks. Non-Security Requirements. Non-security requirements are constraints or specifications that govern a system’s behaviour, performance, and structure without being directly tied to security goals. Unlike security requirements, they do not aim to prevent, detect, or recover from harm, and do not operationalise security policies. They may include functional requirements (which define what the system should do) and other non-functional requirements such as performance, usability, reliability, scalability, and maintainability. Non-security requirements are typically derived from business needs and user expectations but are not intended to address risks, threats, or vulnerabilities. While they may influence system design and operation, they do not explicitly enforce security mechanisms or aim to mitigate security concerns. Functional Requirements. Functional requirements define the essential functions a system must perform, the services it must offer, and the behaviours it must exhibit under specified conditions. They focus on what the system should do—describing actions, operations, or transformations the system executes—without addressing implementation constraints. They typically specify the inputs (stimuli) to the system, the outputs (responses) from the system, and the behavioural relationships between them. In practice, they outline the specific behaviours, features, and capabilities the system must have to meet user needs and achieve its intended purpose, such as user authentication, data storage, report generation, or integration with other systems. Non-Functional Requirements. Non-functional requirements do not define the essential functions a system must perform, the services it must offer, or the behaviours it must exhibit under specified conditions. They do not focus on what the system should do—avoiding descriptions of actions, operations, or transformations the system executes—and instead address implementation constraints. They typically exclude specifications of inputs (stimuli) to the system, outputs (responses) from the system, and behavioural relationships between them. They encompass a system’s quality-related attributes as well as the constraints under which the system must operate—for example performance, scalability, portability, compatibility, reliability, maintainability, availability, security, and usability—specifying how a system should behave rather than what it should do. Quality Requirements. A quality requirement expresses how well a system or service should execute an intended function. Quality requirements include attributes or constraints that address product-quality aspects and quality-in-use aspects. Product-quality aspects include functional suitability, reliability, performance, efficiency, usability, maintainability, security, compatibility, and portability. Quality-in-use aspects include satisfaction, effectiveness, freedom from risk, efficiency, and context coverage. Quality requirements often address the global properties or characteristics of the system rather than those of specific functions. J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.
111:58
Zadenoori et al.
Non-Quality Requirements. A non-quality requirement does not express how well a system or service should execute an intended function. Non-quality requirements exclude attributes or constraints that address product-quality and quality-in-use aspects. They do not include the productquality aspects of functional suitability, reliability, performance, efficiency, usability, maintainability, security, compatibility, or portability; nor the quality-in-use aspects of satisfaction, effectiveness, freedom from risk, efficiency, or context coverage. Non-quality requirements do not typically address the global properties or characteristics of the system; instead, they focus solely on the properties of specific functions. Received 20 February 2007; revised 12 March 2009; accepted 5 June 2009
J. ACM, Vol. 00, No. 0, Article 111. Publication date: January 2026.