Example method includes: identifying three relationships about a network function in an intent-based stateful network—(1) the network function forwarding a network packet implies that at least one previous network packet was received by the network function in the same direction prior to the network packet is forwarded, (2) an established state in the network function implies that at least one previous network packet was received at the network function, (3) the network function receiving the network packet as a downward network function implies the network packet was previously sent by a second network function acting as an upward network function; encoding the network function using a combination of at least one of the three identified relationships; and verifying a plurality of network intents in the intent-based stateful network based at least in part on the encoding of the network function.