GraphSentry: Contract-Checked Graph Surgery for Budgeted LLM Reasoning DAGs

Abstract Budgeted inference-time optimization can improve large language model (LLM) reasoning without weight updates, yet multi-step pipelines are brittle: small edits or crossover between partially correct procedures often violate interface assumptions, triggering late failures and retries. We propose GraphSentry, a certificate-driven topology search framework that turns those implicit assumptions into explicit, auditable interface contracts. GraphSentry represents reasoning procedures as grammar-generated typed DAGs; each node emits an (artifact, certificate) pair, where certificates are deterministic predicates evaluated from logged evidence. During search, GraphSentry performs contract-checked graph surgery (mutation and crossover), rejects incompatible splices at module boundaries, and applies bounded repair (K=3) with downstream-only re-execution. Across seven benchmarks, GraphSentry improves accuracy by +5.3–+10.8 points over baselines while reducing token usage by 29–45% and improving latency by 1.6–2.0×. Across tasks, gains correlate with the prevalence of structural invalidity. Finally, discovered topologies transfer zero-shot across models and outperform native baselines without additional search.