I can't believe no one has mentioned this yet. Traditional complaints from LW backpackers - not enough clothes, especially puffy jacket - to fill stuff sack on cold nights, and air pillows too balloon-like and heavy. Try the tip from Mike Clelland's great little book - possibly the only tip in there that really shocked me (except what he does with perfectly good river rocks).
This is simple and brilliant - bring a number of essentially weightless quart-sized zip-lock bags, fill them with air before you go to bed, and stuff them in a stuff sack. The multiple bags solves the problem of being too balloon-like nicely creating a nice yielding cradle for your head. Very comfy, and really the bags do hold the air! Clelland goes a little hard-core hobo with it and uses one of those onion/potato plastic net sack from the grocery store for this, but I prefer one of those fleece covered nylon jobs that doubles as a clothes bag (1.7 oz for me). When you do have extra clothes you can use them in the bag as well. Mix and match to you own tastes, but you will always have an alternative right there, even when it is cold and you have to wear your puffy jacket. All of this for essentially no weight and volume, but you can count the fleece cover (fraction of an oz) as extra if you want.
Please try it out before you poo poo it - you can test it for free with at home without any trouble. I thought it was nuts, and it pretty much works for me as well as any more bulky pillow. Now I pretty much can't imagine a better, more flexible solution.