@Maxmp Just to give an update this is still happening as of build 802. My observations have been that this happens randomly, although it seems to happen more often if I'm changing tracks. It happens to me multiple times a day. The current playlist is being shuffled then suddenly will start playing from the beginning. Oddly, sometimes the first track in the playlist will start somewhere in the middle of the track, as if the player remembered the current time of the current track and carried that over to the next playing track. This seems to happen regardless of output mode or device.
I am using an LG V40 on 8.1.0, and I had the same issue on my LG V30 running 8.0.0. Both devices had large music libraries (>60gb) stored on an sd card if that helps.
Please let me know if there's any more information I can provide.