CertiJoin: Certified Early Termination for Compound LLM Programs

LLM systems combine many model calls to vote on answers, search for solutions, and coordinate agents, yet their final output is often settled long before the last call returns. We introduce CertiJoin, a runtime verification framework that stops computation the moment it can no longer affect the program's declared output. Adapters declare the output rule and the possible results of each call, and a shared checking core determines when nested decisions and shared dependencies permit cancellation. Certificates bind this evidence to the current program and state. We prove exact output preservation for four join types and for local pruning in composed programs, with no probability calibration. In online nested code validation, the core cuts mean latency by 37.6% and tokens by 32.6% against full execution, preserves every paired success/failure outcome, and matches hand-written short-circuit logic to within 0.27%. In majority voting, CertiJoin preserves all 2,000 paired answers while finishing 84.5% of requests early, and in live serving it cuts mean latency by 27.6% with all 200 answers matching their reconstructed full-run references. CertiJoin also makes published stopping policies exact: when runner-up votes arrive first, they change up to 21.13% of answers, while their certified versions change none.