When a new block comes in each node validates that the transactions in that block spend UTXOs that exist in the UTXO set. If a tx input does not exist in the UTXO set the block is invalid. But you'd have a hard time even constructing such a block template under normal circumstances because nodes also validate each tx input when they first see a transaction come across the p2p network. If the input does not exist in the UTXO set or in the mempool (or I suppose in the same package now that packages are a thing) that tx will get dropped and won't propagate through the network. So really it happens at the block level but practically speaking it happens at the mempool level.