So ... As the battery is used, bonds are formed between oxygen molecules in the air, and the lithium ions on the battery's electrodes. Weight is saved by "borrowing" those O2s from the air, as compared to carrying them around fixed in an oxide. Fine.
Does that mean that as the battery charge is depleted (=it runs out of free lithium ions, I guess), it's mass increases due to all the newly bound oxygen being stored in there? That's counter-intuitive enough to just be awesome!
Also, a large-scale battery whose charge level is directly related to its mass (albeit inversely so, from my intuition) and supports recharging is almost a bit like magic. I hope they pull this off, so I can learn to weigh my car before going on long trips, in the future. :)