I don't think anyone's tried benchmarking protobuf against EXI yet, but I've played around with a .NET implementation (Nagasena: http://openexi.sourceforge.net/) and it does outperform Gzip both for compression efficiency and decompression/runtime performance, so long as you use a schema-accelerated parser. It can infer a schema (turning it into a 'grammar' to use the EXI-specific term), but a properly constructed XML Schema will always be fastest/most efficient, especially in low memory systems.