How and when Android auto connects to a bluetooth device?
AFAIK, Android Bluetooth API does not provide this feature.

I have tried to achieve auto reconnection using BluetoothDevice#connectGatt, with "autoConnect" set to true but it did not work at all.

Like Joe suggested in the comments, I would go for my own implementation, handling both the scanning process and the connection process.