TRUST-REGION SALIENCY-GUIDED LOCAL SEARCH FOR INTERPRETABLE SEQUENCE DESIGN AT FIXED EDIT BUDGETS

Discrete sequence design under a fixed edit budget can match target model outputs, but often returns dispersed, multi-cluster edit sets that are hard to interpret. We present SAGE-TRSwap, a saliency-guided trust-region local search that optimizes the same prediction loss as a Ledidi-style relaxation+pruning baseline (Schreiber et al., 2021) while biasing proposals toward high-attribution regions and enabling budget-preserving SWAP refinements. Across 12 regulatory targets/tracks and 5 random starts per target (60 runs per budget), SAGE-TRSwap reduces edit span and cluster count at all budgets (e.g., mean span 852 →100 and clusters 6.0 →1.2 at B = 40) while maintaining or improving absolute error under fixed budgets.