Self-Structuring Latent Action Spaces for Black-Box Instruction Optimization

Instruction optimization for large language models (LLMs) is a high-dimensional discrete black-box optimization problem in which reliable feedback comes only from costly model evaluations. Existing methods search directly in raw text or use LLMs as high-frequency mutation operators, which makes the search hard to analyze and ties generation-side cost to population size and optimization depth. We propose Self-Structuring Latent Action-Space Evolution (SLAE), which represents each instruction as an integer-coded genotype that selects a syntactic scaffold and slot-wise semantic actions and is mapped deterministically to text. Routine search runs in this categorical genotype space without LLM calls, while the space itself evolves: Dynamic Structural Evolution (DSE) adds newly discovered scaffolds, and Adaptive Action-Space Refinement (${\mathrm{A}}^2\mathrm{R}$) adds slot-level actions when search stagnates. Because genotype coordinates are nominal categories, we show that differential-evolution arithmetic on them depends on how categories are indexed and give a label-equivariant variation rule. Under matched evaluation budgets, SLAE with integer-coded differential evolution achieves the best results on all nine language understanding and generation benchmarks we evaluate. In controlled studies under the main experimental protocol, disabling the expansion mechanisms costs 8.7 accuracy points on AG News and 5.3 on a held-out task with a different model family, while on AG News these mechanisms account for about 0.1% of the measured token budget.