What's the maximum number of moves that can result in a threefold repetition from an arbitrary position? Assume that the fifty-move rule does not require a player to claim a draw. Instead, the game is automatically declared a draw if no pawns have been moved and no pieces have been captured in the last 50 moves.

Hence, we don't need to maintain the entire game history to detect threefold repetitions. We only need to maintain a history of the last 100 positions. Out of these 100 positions, half of them are white-to-play and the other half are black-to-play. Hence, only 50 of these 100 positions could possibly be the same as the current position.

Now, out of these 50 candidate positions if each position is repeated twice then we only have 25 distinct positions which could possibly be the same as the current position. Hence, the upper bound on the maximum number of moves that could result in a threefold repetition is 25.

However, it's very unlikely (dare I say impossible?) that there's a position with 25 possible moves that would lead to a threefold repetition. I believe that the actual number is much smaller. We may never know the exact number. Nevertheless, can you prove that the upper bound is lower than 25?

NB. I'm asking this question because I'm developing a neural network that plays chess. Hence, I'd like to reduce the size of the input to the neural network as much as possible. Providing a history of 25 positions to the neural network is a lot.
Twelve moves is the maximum:

[FEN "5K1k/6p1/6pp/8/8/8/b7/Q7 w - - 0 1"]

1. Qxa2 Kh7 2. Qa3 Kh8 3. Qa4 Kh7 4. Qa5 Kh8 5. Qa6 Kh7 6. Qa7 Kh8 7. Qg1 Kh7 8. Qf1 Kh8 9. Qe1 Kh7 10. Qd1 Kh8 11. Qc1 Kh7 12. Qb1 Kh8 13. Qa2 Kh7 14. Qa3 Kh8 15. Qa4 Kh7 16. Qa5 Kh8 17. Qa6 Kh7 18. Qa7 Kh8 19. Qg1 Kh7 20. Qf1 Kh8 21. Qe1 Kh7 22. Qd1 Kh8 23. Qc1 Kh7 24. Qb2 Kh8 25. Qa3 Kh7 26. Qa4 Kh8 27. Qa5 Kh7 28. Qa6 Kh8 29. Qa7 Kh7 30. Qg1 Kh8 31. Qf1 Kh7 32. Qe1 Kh8 33. Qd1 Kh7 34. Qc1 Kh8 35. Qb1 Kh7 36. Qa2 Kh8 37. Qa3 Kh7 38. Qa4 Kh8 39. Qa5 Kh7 40. Qa6 Kh8 41. Qa7 Kh7 42. Qg1 Kh8 43. Qf1 Kh7 44. Qe1 Kh8 45. Qd1 Kh7 46. Qc1 Kh8 47. Qb1 Kh7 48. Qa1 Kh8


Moving the Queen to a2, a3, a4, a5, a6, a7, b1, c1, d1, e1, f1 or g1 all lead to threefold repetition.

As @RemcoGerlich explained the Black pieces have to reset for the positions to be the same.  Black is resetting after every other move (on moves 2, 4, ..., 48) in the example above which is the quickest possible.  

Thirteen moves would require the Black pieces to reset at least 26 times however Black can reset at most 25 times in 50 moves.