I disagree with your assertion that requirements specify what needs to be built and how.

I have always equated user stories with granular requirements because they are what the user / customer requires, and should never specify how something is built in order to allow some creativity on the part of the development team in common up with the solution.

This is what makes user stories Negotiable - the N in INVEST. They specify what the user requires - the outcome, not the output.