> computational costs alone of doing NLP
The speech recognition part could run on a Pentium 133 in the nineties (Nuance software, Dragon naturally speaking), the Echo device has probably a more powerful CPU than that.
The NLP part could run on the device as well, it's mainly a storage problem, you need dozens of GB, at least 32GB sdcard.
Ideally only the search phrases would be sent to Google/Amazon/etc. That's also how Bill Gates vision was described in his 1995 book The Road Ahead. A personal agent in a wallet PC would surf the information super highway for you. ...well we are "almost" there but with a different solution.