If you somehow manage to run out of both all food and all potions and not good enough of a fighter AND can't solve puzzles in a timely fashion, I'd say that the dungeon has beaten you fair and square.
If you run out of food and simply cannot go on, you reload. Just as if your party was just wiped out by a mob. Death by attrition is still death.
I've got a full party of minotaurs, and I've yet so far to run out of food. I have a whole crate full of it. Really, I have no idea what people are talking about, having food problems.
If anything, they should be increased by a further 30% or so, at least. At least then I'd have a bit of a problem and other groups (that doesn't consist entirely of minotaurs) could still just breeze through it.
mpartel: I just completed the puzzle with respawning legionnaires I assume you're talking about. It seems a little far fetched that solving that particular puzzle would take long enough for you to run out of food, unless you want to grind XP there for many many hours. In any case, I guess theoretically you could always run back to the previous crystal to heal up even while starving.
On the other hand, if you're getting hurt at all while fighting legionnaires in a completely open field by the time you get to that area, you should probably just stop playing games entirely.