Semantic Early-Stopping for Iterative LLM Agent Loops¶

🕒 Published (v1): 2026-06-25 13:24 UTC · Source: Arxiv · link

Why this paper was selected

Replaces fixed iteration cap with semantic convergence signal; drop-in for any Writer-Critic loop

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

TL;DR¶

Fixed iteration caps (max_iterations) waste tokens on easy inputs and truncate hard ones because they are content-blind. This paper proposes Semantic Halting Problem (SHP): halt a Writer→Critic loop when consecutive draft embeddings stop changing (cosine distance + patience window), with a four-level priority cascade and a judge-efficient evaluation protocol. The judge-free variant (entropy_only) cuts 38% of operational tokens at statistically parity quality on HotpotQA, while the full quality-gated variant is counter-productive due to per-round judge cost.

Problem¶

Iterative LLM agent loops (e.g., Writer→Critic) universally use a fixed max_iterations counter as the stopping rule. This is content-blind: it over-spends tokens when the loop converges early and truncates when it hasn't. No principled, cheap, content-aware stopping criterion existed with a formal termination guarantee and honest (non-over-claimed) theory.

Method¶

Each draft $x_t$ is embedded by a local (free) sentence encoder $\phi$ into $e_t \in \mathbb{R}^{384}$, L2-normalized. The per-round semantic distance is: $$d_t = 1 - \frac{\langle e_t, e_{t-1} \rangle}{\|e_t\| \|e_{t-1}\|} \in [0, 2]$$ A four-level halt cascade fires in priority order: 1. Critic approval — critic output starts with "APPROVED" 2. Entropy (judge-free) — $d_t < \varepsilon$ for $k$ consecutive rounds (patience window) 3. No-gain — $\Delta IS_t = IS_t - IS_{t-1} \leq 0$ (requires per-round LLM judge call) 4. Failsafe — unconditional halt at $t \geq T_{\max}$

The Information Score $IS_t = \sum_{m} w_m \cdot \text{metric}_m(x_t)$ aggregates RAGAS metrics (faithfulness, answer relevancy, context precision, context recall); weights $w$ are derived via Shannon entropy, AHP, constrained least-squares, or uniform baseline.

Judge-efficient evaluation protocol: generate one full trajectory per question to depth $T_{\max}$; replay all policies over the identical cached drafts; cache judge calls by draft hash; and separate operational tokens (charged to the policy, including judge calls it triggers) from evaluation tokens (measurement only, never charged).

Theoretical claims are machine-checked: Theorem 1 proves termination in $\leq T_{\max}$ rounds via the unconditional failsafe; Lemma 2 proves halt-priority consistency by sharing a single pure function across live, post-hoc, and replay paths. Semantic non-expansiveness (distances decrease on average across rounds) is demoted to Conjecture 1 — empirically tested, not proven.

Key Contributions¶

Honest, machine-checked theory: termination and well-definedness proven and verified; prior Banach-contraction claim retracted, replaced by an empirical conjecture
Judge-efficient evaluation protocol: trajectory replay + cached judging + operational-vs-evaluation token separation, enabling strictly paired policy comparisons at low cost
Empirical study on HotpotQA (N=60 test): shows entropy_only (judge-free) saves 38% tokens at parity quality; full SHP costs +129% tokens for no benefit; oracle gap (+0.115 IS, $p \approx 4 \times 10^{-11}$) reframes the central open problem as best-round identification, not when-to-stop

Results¶

All results vs. fixed_k6 (6 rounds, 11,070 operational tokens, IS=0.670) on the frozen 60-question HotpotQA test split:

entropy_only (judge-free cosine stopper): −38% tokens, $\Delta IS = -0.004$, $p = 0.81$ — token savings significant, quality loss not detectable
fixed_k3: −53% tokens, $\Delta IS = +0.001$, $p = 0.97$
fixed_k1 (single draft): −86% tokens, $\Delta IS = +0.030$, $p = 0.17$, TOST non-inferior — best practical policy
shp (full cascade): +129% tokens (2.3× baseline), $\Delta IS = -0.004$ — dominated; per-round judge cost wipes out savings
oracle_is (upper bound): +170% tokens, $\Delta IS = +0.115$, $p \approx 4 \times 10^{-11}$ — shows substantial unrealized headroom no online signal reaches
Semantic distance characterization: mean $d_t = 0.040$, median $0.022$; 80% of distances fall below $\varepsilon=0.06$; per-step differences $d_t - d_{t-1}$ significantly negative (Wilcoxon $p = 1.3 \times 10^{-3}$, OLS slope $-0.009$), but only ~5% of trajectories are strictly monotone — justifying the patience window $k=2$

Limitations¶

Noisy LLM judge: per-question IS variance is large enough that strict TOST non-inferiority is not certified for parity-quality policies at $N=60$, despite point estimates within 0.004 of baseline
Benchmark under-exercises iteration: HotpotQA answers are short and often answerable from a single grounded draft; fixed_k1 winning on quality is an artifact of this — long-form generation is needed to test whether iteration ever pays
Single dataset: no external validity established; a second benchmark is required
Small compute budget: 8B judge model used throughout; results with a stronger/human-validated judge are left as a robustness check
Conjecture 1 holds only on average: per-trajectory monotone descent is not guaranteed; Theorem 1 provides the safety net regardless

Relevance to Agentic AI / LLM Agents¶

SHP directly addresses the stopping problem in the canonical Writer→Critic agentic loop — one of the most widely deployed multi-agent patterns — replacing the ubiquitous max_iterations counter with a content-aware, guaranteed-terminating alternative. The key practical finding (judge-free cosine stopping saves 38% tokens at parity quality) is immediately actionable in any iterative agent framework. The oracle gap result ($+0.115$ IS unreachable by any online signal) reframes a core agentic design question: the bottleneck is not when to stop but which round to select, pointing toward offline round-selection or learned best-round predictors as the next frontier. The judge-efficient evaluation protocol — trajectory replay, cached judging, and operational/evaluation token separation — is a methodological contribution applicable to benchmarking any iterative agent policy.