Order-Agnostic Decoding for Sample-Efficient RNA Inverse Folding

RNA inverse folding, the task of designing a sequence that folds into a target structure, is a core computational task in RNA synthetic biology. However, current methods rely on best-of-$N$ screening to compensate for low per-sample reliability and left-to-right autoregressive sequence generation, which locks in upstream nucleotides before downstream pairing partners are observed and cannot natively support in-painting tasks. Here, we introduce an order-agnostic decoder for 2D secondary-structure inverse design, trained under a uniform-permutation distribution over decoding orders. On the OpenKnot Round 7b 240-mer pseudoknot benchmark, our method produces five times as many perfect-structure designs per sample as the strongest autoregressive baseline, while being more sample-efficient, and recovers diversity through order randomization rather than token sampling. To showcase in-painting capability, we perform both motif preservation and motif redesign, with the latter strictly impossible under autoregressive decoding. Together, these capabilities could enable functional aptamer and riboswitch design, and reframe sample-efficient generation as a principled alternative to the dominant best-of-$N$ regime in RNA inverse folding.