The paper says that the biggest delay is in the "scan" phase, just getting a list of all the available APs in the area. This would be the same problem addressed by Apple's "try to associate to all known SSIDs on powerup" approach.

Maybe I'm missing something, but their actual machine learning model seems to address a different problem:

  The final features we choose to train: the connection
  time cost includes hour of day, RSSI, mobile device
  model, AP model, Encrypted

Given this, I they're basically giving lower priority to known incompatible device & AP pairs based on their BSS IDs.

Not sure I like the approach that much, seems an AP running a recent OpenWRT and very reliable would be penalized for having buggy factory firmware.