If they are a reputable SEO, they will provide you with an analysis of your current site, a statement of work for what they will accomplish for their fee, and note that rankings cannot be guaranteed. If they fulfilled the work, you just have to understand how uncertain SEO can be.
Then teach yourself the basics of SEO and save yourself the cash next time.