Backward Completion Pools for Domain-Specific LLM Agents: Soft Search Modulation with Compiled Relaxations

Abstract

Production LLM agents serve repeated requests against fixed applications - booking, CRM, project tracking - where goals recur as templates. Current methods allocate test-time search effort using learned signals (process reward models, self-evaluation), which cost extra model calls, degrade under distribution shift, and cannot be audited. We propose backward completion pools: for each goal template, a relaxed backward structure is compiled once from the application's action schema; at serving time a deterministic query binds each request's parameters, and every step of the agent's forward search is joined against the pool, yielding a completion-value estimate at zero model-call cost. The estimate never prunes: it softly modulates each branch's expansion rate under an activity floor, for which we prove completeness in the limit and, under bounded per-node inflation, bounded suboptimality. On Blocksworld with an optimal-cost oracle, the individuated join signal ranks states with Spearman rho = 0.967 versus 0.76-0.79 for same-cost LLM self-evaluation (p < 10^-7). On WorkBench (690 tasks, five workplace applications), all 69 goal templates compile and binding grounds 100% of tasks exactly; ungrounded shape statistics beat LLM signals for cross-request budgeting, while grounded joins dominate within-task discrimination. End-to-end at matched budget (17 calendar tasks x 4 budgets x 3 independent runs, every arm's signal calls charged to the same budget), grounded reallocation solves 29% versus uniform's 16% at the sparsest feasible budget (paired sign test +7/-0, p = 0.016 uncorrected), converging at generous budgets. Self-evaluation, paying its own evaluation calls under the same accounting, solves no tasks in that regime and trails at every budget. The gain is consistent with horizon extension: at budget 16, uniform solves 0/9 length-4 tasks; grounded solves 5/9. Compiled goal structure can thus substitute for learned guidance exactly where serving budgets are tight.