acceptodds
Under review as a conference paper at ICLR 2027

OrderCover: Structure-Aware Budgeted Search over Prompt-Component Orders

Abstract

Prompt optimization typically rewrites instructions or selects demonstrations, although reordering existing components can change model behavior while keeping their text fixed. We formulate fixed-content prompt-order optimization and introduce OrderCover, a budgeted method that selects candidate permutations using structural feature coverage and Kendall-distance separation. Candidate construction uses only permutation structure, without labels, logits, gradients, or model scores. We evaluate OrderCover through complete landscapes across 10 tasks and 7 models, held-out application prompts, and composition with GEPA and MIPROv2. In the controlled suite, OrderCover improves the original Anchor by 3.35 percentage points, recovers 82.99% of the available Anchor-to-Oracle headroom, and exceeds budget-matched Random by 0.46 points. On application prompts, it improves Anchor in 12 of 15 cells, although the aggregate confidence interval includes zero. After content optimization, order search adds 1.48 points on average across 24 cells and improves 19 of them. Order headroom persists for strong starting orders and after content optimization, although the advantage over budget-matched Random is modest. OrderCover offers a transparent, content-preserving post-processing step for prompts whose components can be moved as whole units.

Primary area:
foundation or frontier models, including LLMs
Keywords:
prompt optimization, prompt engineering, large language models, prompt component ordering, order sensitivity, budgeted combinatorial search

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_reBDOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduces OrderCover, a structure-aware method for budgeted prompt-order optimization that preserves the original prompt content. The central motivation is that language models can be sensitive to the ordering of prompt components, while existing prompt optimization methods primarily modify instructions or demonstrations. OrderCover first decomposes prompts into validated, movable components and then selects candidate permutations using precedence, directed-adjacency, coarse-position coverage, and Kendall-distance separation. Candidate construction does not require model outputs or task labels, although selecting the best candidate requires labeled development evaluations. The empirical evaluation covers 70 controlled task–model landscapes, 15 held-out application-prompt settings, and 24 post-content-optimization settings. In the controlled suite, OrderCover improves Anchor accuracy by 3.35 percentage points, captures 82.99% of the available in-sample headroom, and exceeds budget-matched Random search by 0.46 points. On application prompts, the mean improvement over Anchor is 3.32 points, but its confidence interval includes zero. After GEPA or MIPROv2 optimization, additional order search improves held-out accuracy by 1.48 points on average. The evidence supports prompt ordering as a useful optimization dimension, while the incremental benefit of the proposed selector and its generalizability remain more limited.

Critical strengths
  1. Sections 3.1–3.2 establish a clear distinction between modifying prompt content and modifying component order. The decomposition and grouping procedure preserves the exact text and within-component order, with deterministic reconstruction checks described in Appendix A. This provides a useful experimental intervention for investigating order sensitivity without conflating it with textual rewriting. The explicit restriction to independently movable components also makes the method's intended scope relatively clear. The formulation is valuable because it isolates an optimization dimension that can be investigated independently of conventional content optimization.

  2. Section 6.1, Table 1, and Appendix D provide complete permutation landscapes across ten tasks and seven models, enabling direct measurement of attainable in-sample order headroom. OrderCover achieves 67.38% accuracy compared with 64.03% for Anchor, 66.92% for budget-matched Random, and 68.00% for Oracle. Its 0.46-point advantage over Random has a reported 95% bootstrap interval of [0.21, 0.83]. Random search is averaged over 10,000 independently sampled candidate sets, and both methods include Anchor under equal evaluation budgets. These controls make the comparison informative and distinguish the substantial benefit of searching over orders from the smaller incremental benefit of structure-aware candidate selection.

  3. Section 6.3, Table 2(b), and Appendix F investigate whether optimized prompts retain useful order headroom. After freezing prompts produced by GEPA or MIPROv2, OrderCover improves held-out accuracy in 19 of 24 cells, with four ties and one loss. The aggregate improvement is 1.48 percentage points, with a reported 95% interval of [0.94, 2.06]. Both GEPA and MIPROv2 show improvements, suggesting that content optimization does not necessarily exhaust the potential benefits of reordering instructions. The use of disjoint test sets provides stronger evidence of practical value than the controlled landscapes alone.

Critical weaknesses
  1. The principal algorithmic contribution is the combination of structural feature coverage, Kendall separation, and anchor-distance balancing in Equation 6. However, Table 1 shows that budget-matched Random already recovers much of the available order headroom. More importantly, Appendix B.5, Table 5, reports 67.38% accuracy for the full selector versus 67.30% for Kendall farthest-first and 67.27% for the unbucketed hybrid. These differences of 0.08 and 0.11 percentage points are small, with many pair-level ties. Although the ablations support a modest aggregate advantage, they do not establish that the complete structural design yields a practically substantial improvement over simpler diversity-based selection. This distinction matters because the stronger empirical contribution may be the usefulness of budgeted order search itself rather than the specific OrderCover scoring rule.

  2. The controlled evaluation in Section 6.1 selects and scores permutations on the same evaluation set. Consequently, its Oracle headroom and recovered-headroom measurements are descriptive in-sample quantities rather than estimates of deployable test improvements. The paper appropriately includes a separate held-out application suite, but Table 2(a) reports a mean improvement over Anchor of 3.32 points with a 95% interval of [−0.43, 8.69]. The advantage over Random is 0.84 points with an interval of [−0.02, 1.13]. Neither interval excludes zero. Furthermore, Appendix E, Table 16, reports a particularly large 22.00-point improvement for LlamaIndex with Ministral-3-8B, illustrating substantial variation across cells. These results suggest that beneficial orders frequently exist, but they do not establish a consistently positive average improvement across unseen applications or a reliably superior selector in that regime. The uncertainty should not be interpreted as evidence of equivalence or ineffectiveness.

  3. Sections 3.1–3.2 and Appendix A validate component types, grouping contiguity, and exact-text reconstruction. However, these checks do not establish that every resulting permutation preserves the intended semantics or instruction dependencies. This is particularly relevant when reordering directives, constraints, label definitions, and instance inputs. The authors acknowledge this limitation in Section 8. Furthermore, Appendix G.1, Table 21, reports exact component-count agreement of only 41.3% and 42.1% for two alternative decomposition models, despite much stronger agreement on whether prompts have at most six components. The structuralization sensitivity analysis does not directly evaluate whether alternative decompositions preserve OrderCover's downstream accuracy gains or its advantage over matched Random search. Therefore, stability of the component-count regime should not be interpreted as robustness of the complete optimization pipeline.

  4. Section 5.3 and Appendix F demonstrate residual order headroom after content optimization, but the experiment uses one saved artifact from one seed per optimizer configuration. Appendix F.2 also specifies an instruction-only MIPROv2 configuration with demonstration optimization disabled. Thus, the reported results characterize these particular optimizer outputs rather than the variability of order-search benefits across independently optimized prompts. Moreover, the post-optimization suite has no budget-matched Random arm, so we cannot attribute its 1.48-point improvement specifically to the proposed structural selector. Appendix C.2 additionally computes its confidence interval by resampling 24 cell-level differences, although these cells reuse tasks and models. This interval describes variability across the observed cells but does not fully establish uncertainty across independent tasks, models, or optimizer seeds. These limitations do not negate the observed improvements, but they constrain the interpretation of complementarity and robustness.

  5. Section 8 and Appendix D.3, Table 14, show that all controlled experiments involve at most six components. For four components, the evaluation budget covers 16 of 24 possible orders, making the search relatively close to exhaustive. For six components, only 36 of 720 orders are evaluated, but the seven corresponding task–model pairs all share one task. Appendix B.3 describes extending the selector to larger spaces through sampled candidate pools, without evaluating this extension. Consequently, the experiments demonstrate effectiveness in small enumerable spaces but do not establish how selection quality or computational cost behaves for larger prompts requiring genuinely sparse exploration. The paper explicitly acknowledges this boundary, but it remains important for assessing the practical reach of a budgeted search method.

Questions for authors
  1. Given the small differences from Kendall farthest-first and the unbucketed hybrid in Appendix B.5, could the authors report paired uncertainty estimates for these comparisons? If feasible, evaluating Kendall farthest-first under the same development/test protocol as the application suite, with identical componentization, candidate budgets, and selection data, would help determine whether the full structural objective provides benefits beyond generic permutation diversity.

  2. Could the authors provide application-stratified paired differences and a leave-one-application-out analysis for Table 2(a), particularly accounting for the large LlamaIndex–Ministral improvement in Table 16? This would clarify whether the observed average gain reflects recurring improvements across applications or substantial dependence on particular settings. An explanation of which prompt characteristics are associated with stronger gains would also improve the practical interpretation.

  3. Appendix G.1 establishes component-count agreement but not performance stability. Could the authors evaluate a small representative subset using the alternative decompositions already generated, while holding prompt text, target model, development/test examples, and evaluation budget fixed? Reporting differences in selected orders, held-out performance, and comparisons with Random would directly assess whether decomposition variability materially affects the method's benefit. A brief audit of cross-component semantic dependencies would additionally clarify the conditions under which arbitrary permutation is appropriate.

  4. Could the authors provide a budget-matched Random comparison for the existing frozen GEPA and MIPROv2 prompts, using the same development splits and test metrics? Additionally, is there evidence from alternative optimizer seeds, or an analysis indicating how artifact variability might affect the results? A task-clustered uncertainty analysis would help distinguish variation across genuinely different tasks from repeated measurements involving the same tasks and models. If additional runs are infeasible, explicitly limiting the conclusions to the evaluated optimizer artifacts would resolve part of this concern.

  5. Appendix B.3 proposes candidate-pool sampling for larger component counts. Could the authors clarify how they would choose pool size, global versus local sampling, and greedy-selection cost? A controlled comparison using the existing six-component landscapes, where the candidate pool is artificially restricted while holding the evaluation budget fixed, could provide preliminary evidence about sensitivity to pool construction without requiring substantially larger experiments. This would help assess whether the proposed method's benefits extend beyond direct enumeration of small permutation spaces.

1 comment

Thank you again for your detailed reviews. As the discussion phase closes on November 18, we would like to check whether our response and revised Appendix H have addressed your concerns (about paired uncertainty, application-level influence, semantic dependencies, the post-optimization Random arm, and restricted candidate pools). We would be glad to clarify any remaining points or provide additional analysis.

Reviewer_TgPHOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper treats the order of prompt components, such as instructions, label definitions and examples, as something to optimize while keeping their text unchanged. Its method, OrderCover, picks a small, structurally diverse set of orders to try without using model scores and then keeps the best one. Using complete order landscapes for several tasks and models, the authors show that reordering recovers most of the available gain, a bit more than random search with the same budget, and that order still matters for real application prompts and for prompts already tuned by content optimizers.

Critical strengths
  1. The evaluation is careful and honest. Trying every possible order for 70 task–model pairs gives an exact reference for judging a budgeted search method. The error bars cover both task and model variation, and the held-out suites keep selection and testing separate. The paper is also open about where its evidence is weak (an interval that includes zero, a small edge over random, no random arm in one suite). That care is why the paper is useful even though the gains are small.

  2. The practical finding is useful: order still matters even when the starting prompt is already good, and even after GEPA or MIPROv2 have tuned the content. Reordering costs nothing at deployment time, so it is a cheap extra step people can actually use.

Critical weaknesses
  1. The part that is specific to OrderCover adds very little, and the tests are in a setting where budgeted search barely matters.
  • It beats random search with the same budget by about half a point. It beats a standard "pick orders far apart in Kendall distance" baseline by less than a tenth of a point, with most pairs tied. So the feature-coverage idea, the new part of the method, isn't shown to help beyond plain diversity.
  • There are at most six components, and the budget is M². With four components the method already tries two thirds of all orders, and only one task has six. The case it is built for, where the budget is a tiny slice of all orders, is barely tested.
  • Everything uses one budget. The full landscapes already exist, so a budget sweep would cost nothing and would show where the method actually helps.
  • There are no adaptive baselines, like hill-climbing from the original order or successive halving, even though the chosen orders get scored on labeled data anyway. The diversity weight was also tuned on most of the same evaluation pairs, though its effect looks flat.
  1. Several gains over the original order are too optimistic, or miss the control needed to credit OrderCover.
  • In the controlled suite, selection and scoring use the same examples, so the gain over the original order includes some "best of many" luck. The comparison with random is fair, because both share that luck. Selecting on half the examples and scoring on the other half would fix this.
  • On real application prompts, one cell drives the average gain over the original order. Without it the average is about two points, and the interval includes zero.
  • The post-optimization suite has no random arm and no compute-matched control. So it shows there is room to gain, not that OrderCover is the right way to get it. The optimizer baseline also looks weak: one seed, MIPROv2 without demonstrations, and worse than the original prompt on held-out data in a quarter of the cells.
  • The search space depends on an LLM that splits the prompt into parts. Other LLMs agree with it on the exact number of parts only about 40% of the time, which hurts reproducibility.
Questions for authors
  1. Can you report the controlled-suite results with selection on one half of each cell's examples and evaluation on the other half?

  2. Using the existing landscapes, how do OrderCover, random search and Kendall farthest-first compare across budgets, especially with five or six components?

  3. In the realistic suite all orders were scored on dev. What does just picking the dev-best order give on test?

  4. In the post-optimization suite, what do a random-order arm and an optimizer given the same extra dev evaluations get?

  5. How were the 8 evaluation tasks picked from the 49 candidates? Was order headroom looked at beforehand?

5 comments
AuthorsOpenReview ↗

Official Comment by Authors [1/2]

Thank you for the specific questions and for separating ordering headroom from the incremental contribution of OrderCover. All new analyses are reported in Appendix H of the revised PDF.

Q1. Selection and evaluation on disjoint halves.

For all 70 controlled task–model combinations, we use 30 random 500-development/500-test partitions of each task's 1,000 examples, shared across models and methods. Each method receives the default budget (16/25/36 orders for four/five/six components, including the original order). The highest-development-accuracy candidate is frozen and scored on the other half; ties use the lowest permutation index, never test accuracy. Random samples the remaining orders uniformly without replacement and averages over 10,000 candidate sets. Splits are averaged within each combination before tasks and models are resampled (Appendix H.1).

MethodDevelopment accuracy (%)Held-out test accuracy (%)Test gain vs original, pp [95% interval]Wins / ties / losses vs original
Original order (Anchor)64.11563.9480.000 (reference)—
Random67.22466.211+2.263 [+0.962, +3.943]56 / 0 / 14
Kendall farthest-first67.58166.631+2.683 [+1.217, +4.471]54 / 1 / 15
OrderCover67.69466.651+2.703 [+1.235, +4.524]52 / 0 / 18
Exhaustive development-set selection (Q3 reference)68.36367.094+3.146 [+1.445, +5.208]58 / 0 / 12

OrderCover improves held-out accuracy by 2.703 points [1.235, 4.524] (in-sample: 3.35). Its paired margin is +0.440 [0.165, 0.771] over Random and +0.020 [−0.462, +0.556] over Kendall farthest-first. The ordering benefit therefore persists on held-out examples, with a modest margin over Random and little separation from Kendall farthest-first. The exhaustive row is not budget-matched (see Q3).

Q2. Budgets, adaptive search, and λ.

Keeping the original initialization, we reduce the number of evaluated orders to as few as 10 for five components and 12 for six components, i.e., 1.67%–5% of the 720 six-component orders (Appendix H.6):

Budget: five componentsBudget: six componentsOrderCover–Random (pp)OrderCover–Kendall farthest-first (pp)
1012+0.662+0.325
1218+0.674+0.360
1824+0.597+0.171
2536+0.516−0.034

All eight simultaneous 95% intervals include zero. The point estimates suggest a modest Random-relative margin across budgets, but do not establish that the margin grows at smaller budgets or that feature coverage is necessary; the six-component group is one task evaluated on seven models.

Under the same budget, restart hill-climbing reaches 66.72% versus 66.65% for OrderCover (difference −0.07 [−0.50, 0.33]), but requires 10.06 sequential feedback rounds on average, whereas OrderCover's candidates can be evaluated in one batch. We infer no latency speedup from this count.

λ=0.6 was selected without the 20 combinations involving Gemma-4-31B and gpt-oss-120b. On these, OrderCover–Random is +0.65 [0.21, 1.33]; this is a two-model holdout on the same tasks. Retrospective nested tuning changes OrderCover's overall mean by −0.006 points, and we do not claim that λ=0.6 is uniquely optimal.

Q3. Exhaustive development-set selection.

For the realistic suite with Gemma-4-31B and Ministral-3-8B (ten settings; the five GPT-5.6 Terra settings are not included), we score all 24 or 120 orders on the 100 development examples and evaluate the development-best order on the 200 test examples. Per-setting results are in Appendix H.7.

MethodEqual-weight mean (%)Development-evaluated orders per setting
Anchor70.432—
Random74.07321.4
OrderCover74.69021.4
Exhaustive development-set selection74.79381.6

Exhaustive selection exceeds OrderCover by +0.103 [−0.830, +0.750] (6/1/3 wins/ties/losses) and Random by +0.720 [+0.099, +1.370]. It gains 1 point on both LlamaIndex settings but loses 2 points on Steamship–Gemma, so searching the full development space does not guarantee a better held-out result; these results do not establish equivalence between the selectors. In the controlled suite (last row of the Q1 table), exhaustive selection over all 24/120/720 orders reaches 67.094% versus 66.651% for OrderCover, using 141.6 versus 22.5 evaluated orders on average.

AuthorsOpenReview ↗

Official Comment by Authors [2/2]

Q4. Random after content optimization, and further optimizer search.

For all 24 optimized settings, we added a budget-matched Random arm and, separately, continued the same optimizer (GEPA or MIPROv2, instruction-only, fresh optimizer state) from the same optimized instructions. All arms select on the same 100 development examples and are scored on the same 200 test examples (Appendix H.3). Development budgets match OrderCover in 21 of 24 settings; three Terra MIPROv2 settings differ (further optimization / OrderCover: MultiRC 2,500/3,600, NLI 2,400/1,600, StereoSet 2,400/1,600).

PanelOptimized original+ Random+ OrderCoverFurther same optimizerFurther − OrderCover, pp [95% interval]
GEPA: 12 settings71.58372.45872.91770.375−2.542 [−4.458, −0.792]
MIPROv2: 12 settings69.29270.54270.91769.167−1.750 [−4.917, +0.750]
All 24 settings70.43871.50071.91769.771−2.146 [−4.146, −0.604]

OrderCover improves over the optimized original order by +1.48 points (19/4/1; crossed interval [0.52, 2.44], task-cluster [1.04, 1.98]). Its margin over Random is +0.42 [−0.44, 1.21] (11/7/6), so OrderCover superiority after content optimization is not established.

Further optimization trails OrderCover in 18 of 24 settings (4 wins, 2 ties) and, on average, falls below its own starting prompts (69.77% vs. 70.44%), suggesting that further editing selected on 100 development examples can overfit. It can still help individual settings: on Terra, further MIPROv2 improves its starting prompts (76.250% → 77.625%) and beats OrderCover on Math MCQA (76.5% vs. 73.5%), while its four-task mean stays below OrderCover's 77.875%. These results support residual ordering opportunity after content optimization, not that reordering is universally preferable to further editing; the scope remains four tasks with one saved initial prompt and one optimization seed per configuration.

Q5. Selection of the eight Super-NaturalInstructions tasks.

The eight tasks were selected before we inspected task accuracies or order headroom, to cover different prompt structures while keeping complete permutation landscapes. All 49 candidates passed the decomposition checks (Appendix A.2), so no exclusion was a decomposition failure. We grouped candidates by component count and structural pattern (the ordered sequence of component types); the 41 exclusions are (Appendix H.8):

Exclusion categoryTasksReason
Repeated structural patterns29Component-type sequence already represented among the selected tasks.
Rare or atypical structural variants9Pattern occurring fewer than three times in the pool, or atypical component placement.
Three-component prompts3Only six possible orders, all covered by the default budget.

For example, 14 candidates share the pattern input description → directive → demonstrations → instance input; we kept three with different prompt lengths (CrowS-Pairs stereotype category, MathQA, and Math MCQA). The selected tasks span four to six components, 533–1,436 characters, and eight component types. Excluding rare variants limits coverage of unusual structures; the suite characterizes these structures rather than average order sensitivity across Super-NaturalInstructions.

Application heterogeneity and decomposition.

Omitting the LlamaIndex/Ministral-3-8B setting reduces OrderCover–Anchor from +3.32 to +1.99 points, and leave-one-application-out means range from +1.90 to +3.90 (Appendix H.4); the hierarchical intervals are [−0.43, 8.69] against Anchor and [−0.02, 1.13] against Random. Our component audit found cross-block references and grammatical continuations that require stronger grouping or precedence rules (Appendix H.5), and we have not completed a downstream comparison under alternative decompositions; Section 8 now states both limitations.

Thank you again for your specific questions. With the discussion period ending on November 18, we wanted to check whether our response and revised Appendix H (Appendix H.1: selection and evaluation on disjoint halves, H.6: the reduced-budget and λ-holdout analyses, H.7: exhaustive development-set selection, H.8: task-selection procedure, and H.3: the comparison with further optimization by the same content optimizer) address your concerns. We would be glad to clarify any remaining point or provide additional analysis.

Reviewer_1FsJOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

OrderCover studies fixed-content prompt-order optimization, where existing prompt components are reordered without changing their text. It proposes a structure-aware search method that selects permutations based on feature coverage and Kendall distance. Experiments across 10 tasks and 7 models show improvements over the original prompt order and a modest advantage over budget-matched random search. Additional held-out experiments show gains on application prompts and after GEPA or MIPROv2 optimization.

Critical strengths
  • Broad evaluation with consistent evidence of order headroom. The controlled study covers 70 task–model pairs, and the held-out experiments extend the analysis to application prompts and content-optimized instructions. The reported gains after GEPA and MIPROv2 are particularly useful evidence that content optimization does not exhaust order-level improvements.
Critical weaknesses
  • I find the problem and approach lacks of motivation. Order optimization is a really sub problem in the prompt optimization space, and the gain against random appears to be modest. It is unclear intuitively how changing the order could help and empirically whether the modest gain is overfiting.

  • The baseline is incomplete. Please add more baselines on prompt optimization.

  • The model used in the experiments are predominately small models. It is unclear whether the prompt order matters in frontier models who has superior intelligence, and whether the performance gain still persist.

Questions for authors

N/A

1 comment

Thank you again for your review. As the discussion period ends on November 18, we wanted to check whether our response and the revised Appendix H address your concerns (Appendix H.1: held-out results that separate order selection from scoring, and H.3: compares ordering with a budget-matched Random arm and with further content optimization. We would be glad to clarify any remaining points or provide additional analysis.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.