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

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.