It's app data, emails, messages etc.
Deleting my messages cleared up 2.5 gb of other space on my iPhone. I'm in a few group messages though, lots of pics and videos though.
You can also go through each app and under setting > general > usage and when you click on them check their Documents & Data. If some are very high you'll have to delete and reinstall the app (you'll lose that data beware).
In rare cases its some sort of corruption and a restore from NEW is the only solution.