Multi-context FPGAs are a convenient solution for runtime reconfiguration, but they suffer from large area occupation. This is mainly due to programmable interconnect configuration memories which need to be replicated as many times as the number of contexts. To overcome this limitation a new decoder-based interconnect architecture is proposed. Dramatic improvements in terms of area and delay with respect to previous approaches are presented, such that multi-context FPGAs can finally become a viable solution for next generation configurable devices.