Can you give us a little more detail about the nature of your data and calculations? Is your entire data set 5k records, or just the amount you're returning from your query? If you've got a million records but have a filter that limits your data set to 5,000 then it's going to take a little while for the query to run against every row of your vertica table.
If you've got a super wide data set, that could also slow things down a little. Tableau runs better with tall data then wide. You said that you currently have a live connection to vertica, but it might be interesting to create an extract and run from that, to see how much of a difference it makes.
If your LOD calculations are particularly complex (perhaps a calculation that includes several different nested LOD calcs at different aggregation levels) it might slow things down too, as it would have to re-query the same table several times per returned record. I'm not positive on this one, but it came to mind as a possible bottleneck.