Audit-First Recombination for Test-Time LLM Optimization Under Deterministic Verifiers

Deterministic verifiers make test-time optimization of large language model (LLM) outputs practical, but modern search pipelines still waste budget on candidates that are structurally ineligible for semantic evaluation. Ineligibility includes parse failures, schema violations, and dependency breaks. These dead-on-arrival candidates consume the same scarce backend capacity as informative trials, reduce throughput under rate limits, and make cross-candidate reuse brittle under strict verifiers. We introduce audit-first recombination, a primitive for verifier-backed generation whose central operation is a deterministic compatibility decision for cross-candidate edits before verifier execution. We represent each candidate as an interface-typed reasoning DAG. We emit an untrusted per-edit certificate. We require every nontrivial edit to pass a deterministic structural gate before any verifier execution. The gate checks acyclicity. It checks namespace closure. It checks schema and terminal validity. It checks interface compatibility. The gate certifies structural eligibility only. Correctness remains entirely defined by the external verifier. We instantiate the primitive in Genetic Inference Search (GIS) with certificate-gated recombination (SemanticGraft). We add a stricter deterministic precondition layer (Cert++). Under strictly matched per-instance token budgets that charge all LLM calls, GIS+Cert++ improves accuracy by 4.2-10.3 points over strong same-budget baselines. It reduces wasted verifier executions. On SWE-bench Verified ($n{=}300$), it increases resolved by 7.6 points relative to Agentless. It uses 38% fewer test runs. Targeted audits show that adding Cert++ preconditions consistently reduces runnable-but-mismatched edits without changing the verifier, and that interface extraction degrades gracefully when symbol metadata is sparse. Finally, we report per-edit diagnostics (CertPass, GVR, CUR, PatchSz). They make reuse auditable and falsifiable in deployment.