Hi, I'm Jim (@JimLarson), another CEL maintainer. Yes, the full language spec is more clear about the performance limits, and macros can easily result in exponential time or space complexity. The original claim could be for either the macro version or the equivalent expanded version, e.g. "[true, false].exists(v1, [true, false].exists(v2, ... [true, false].exists(vN, (v1 || !v2 || v3) && (v2 || v3 || !v4) && ...)...))", etc. But it doesn't require much power in the language to express this kind of "solver" - there's still no general recursion.