Bicep and Azure Resource Manager (ARM) are able to dispense with state only because every Azure resource is required to be individually addressable and to report its state in a consistent way, and each resource is expected to support fully idempotent creation operations. The state information is still there, but it's stored on the resource itself.

Bicep/ARM still has issues with resource deletion, though. The default deployment behavior is to ignore resources that aren't described in a deployment template, so if you remove a VM from your template and redeploy, the VM will keep running until you manually delete it. There are a couple ways around this issue, but they all rely on having state external to the resource itself.

Disclaimer: I work on Bicep/ARM and think it's pretty great, but it's not perfect.