Leonin Arbiter‘s static ability prevents player from searching their libraries unless they pay 2 mana. Paying this mana is a special action that can only be done when a player has priority. Technically speaking, in order to search your library you must pay this two mana before any effect that would allow you to search starts to resolve.
For example, if you were to cast Memoricide, you need to pay 2 mana to satisfy Leonin Arbiter’s ability before passing priority to your opponent. Otherwise your opponent can pass priority back at which point the Memoricide will start to resolve and it will be too late to pay this mana.