In this paper, we propose BOOST, a bootstrapping-based framework to overcome the limitations of existing few-shot learning methods in program-guided inference for complex assertion verification. BOOST integrates assertion decomposition and information gathering strategies as structural guidelines for program generation, iteratively improving bootstrapped demos without human intervention. This enables a smooth transition from zero-shot to few-shot strategic program-guided learning, thereby improving interpretability and efficiency. Experimental results show that BOOST outperforms existing few-shot baseline models in both zero-shot and few-shot settings for complex assertion verification.