Efficient way to deal with maintaining Many:Many relationships in EF Code-First
I know this is an old question, but I think the problem is timeless. Many to many associations (i.e. without junction class) in Entity Framework are always independent associations, so you can only establish or remove them by manipulating object collections, not primitive key values. Inefficiency is inherent to the implementation.  

But it is not prohibited to have a second context that only contains junction tables.

You could create a context that contains the MasterInstanceInstaller junction table and use this to update the associations in the most efficient way you can get using EF:

var installer = installerModel.Installer;

var junctions = context.MasterInstanceInstallers
                       .Where(x =&gt; x.InstallerId == installer.InstallerId)
                       .ToList();

// Delete deselected instances.
foreach(var mi in junctions
                  .Where(x =&gt; !installerModel.SelectedMasterInstances
                                             .Contains(x.MasterInstanceId)))
{
    context.MasterInstanceInstallers.Remove(mi);
}

// Add newly selected instances.
foreach(int instanceId in installerModel.SelectedMasterInstances
                                        .Except(junctions.Select(j =&gt; j.MasterInstanceId)))
}
    context.MasterInstanceInstallers.Add(new MasterInstanceInstaller
                                             {
                                                InstallerId = installer.InstallerId,
                                                MasterInstanceId = instanceId
                                             }
                                        );
}
context.SaveChanges();


Now, if necessary you can populate the updated many to many association through the main context.