Vlad I believe it may be related to that, yes.
In terms of reproducing, it's more noticeable when typing quicker, so that may be something to attempt. However, it doesn't seem to lag or stutter when typing randomly (ie. not real queries), which supports the idea that it may be tied to the history/bookmarks.