Alright, this has driven me crazy for over a week and I couldn’t find an answer anywhere on the web so I decided to dive into Mastodon’s code.
The solution is simple: both followers and following need to be paginated, even if either of them is empty. Mastodon retrieves both and simply checks if they have a “first” property. That’s it.