Technical Summary: State Representation and Termination for Recursive Reasoning Systems

1. Problem Statement

Recursive reasoning systems—encompassing iterative retrieval-augmented generation, agent action-observation loops, tree-of-thought reasoning, and continual learning—operate by alternating between acquiring new evidence and refining an accumulated internal state. Despite their diversity, these systems currently suffer from two critical design gaps:

1. Implicit State Representation: Current systems often represent reasoning states as transient text traces or hidden activations. This lack of structured, persistent state prevents the system from explicitly tracking which claims are supported, which are in conflict, and which questions remain unresolved. Consequently, contradictions accumulate undetected, and the system cannot determine what information is still missing.
2. Exogenous Termination Criteria: Termination is typically imposed by fixed limits (e.g., maximum depth, token budget, or iteration count) rather than derived from the system's internal dynamics. This leads to characteristic failure modes: premature stopping on complex tasks, redundant processing on simple tasks, and "hallucinated" improvements where self-refinement degrades performance due to a lack of convergence signals.

The paper argues that without an explicit state and an endogenous termination criterion, recursive systems cannot reliably detect when they have settled on a solution or when further iteration is beneficial.

2. Methodology

2.1. Epistemic State Graph

To address the state representation gap, the authors propose the Epistemic State Graph ($S$), a structured graph defined as a tuple $(V, E, \ell, c, w)$:

• Nodes ($V$): Partitioned into Claim nodes (extracted facts), PartialAnswer nodes (current best answers), and OpenQuestion nodes (identified but unresolved dependencies).
• Edges ($E$): Typed directed edges representing Supports (evidential backing), Requires (logical dependency on unresolved evidence), and Contradicts (inconsistency).
• Attributes: Nodes and edges are weighted by confidence ($c$ and $w$) and encoded with attribute vectors ($\ell$).
• Embedding: To facilitate mathematical analysis, the discrete graph is embedded into a fixed-dimension Euclidean space ($\mathbb{R}^d$) via a smooth map $\phi$. This allows the reasoning operators to be treated as differentiable functions, enabling the use of calculus-based convergence analysis.

2.2. Expansion and Consolidation Operators

The system's dynamics are formalized through two operators acting on the embedded state $\theta_t$:

• Expansion ($P_e$): Incorporates new external evidence $e$. In the graph context, this adds new claim nodes, links them via typed edges, and resolves open questions.
• Consolidation ($Q$): Refines the state using only existing information. This involves resolving contradictions (downweighting lower-confidence claims), merging redundant nodes, and shifting weight toward the best partial answer.
• Dynamics: The system evolves via $\theta_{t+1} = Q(P_{e_t}(\theta_t))$, where $e_t$ is sampled from a distribution dependent on the current state.

2.3. Order-Gap Termination Criterion

The core innovation for termination is the Order-Gap ($\Omega$), which measures the non-commutativity of the expansion and consolidation operators.

• Definition: $\Omega(\theta; e) = \|Q(P_e(\theta)) - P_e(Q(\theta))\|$.
  • $Q(P_e(\theta))$: The actual system trajectory (expand then consolidate).
  • $P_e(Q(\theta))$: A hypothetical trajectory where consolidation happens before expansion.
• Logic: If the order of operations significantly changes the outcome (large $\Omega$), the system is sensitive to new evidence and has not yet settled. If the order does not matter (small $\Omega$), further iteration is unlikely to change the result materially.
• Stopping Rule: Iteration halts when a windowed average of the order-gap, $\hat{\Omega}_{t,w}$, falls below a threshold $\epsilon$.

2.4. Non-Degeneracy Analysis

The paper provides a theoretical guarantee (Theorem 5.2) ensuring the criterion is informative. It establishes a local non-degeneracy condition for the linearized commutator Gramian ($G_{\theta^*}$). The condition states that the order-gap is not algebraically zero (i.e., it is a valid signal) if and only if the intersection of the kernels of the linearized commutators for all possible evidence items is trivial. This ensures that a small order-gap reflects true convergence rather than a mathematical artifact.

3. Key Contributions

1. Epistemic State Graph: A formal, structured representation for reasoning states that explicitly tracks claims, conflicts, dependencies, and confidence, enabling principled expansion and consolidation.
2. Operator Framework: A rigorous definition of expansion and consolidation operators on a smooth Euclidean embedding of the state graph, facilitating dynamic analysis.
3. Order-Gap Termination: A novel, endogenous stopping criterion derived from the system's operator structure. It measures the sensitivity of the state to the ordering of operations.
4. Non-Degeneracy Theorem: A necessary and sufficient condition (Theorem 5.2) characterizing when the linearized order-gap is non-degenerate near a fixed point, ensuring the criterion is not vacuous.
5. Generalizability: A demonstration that this framework applies across diverse architectures, including recursive language models, agent loops, tree-of-thought reasoning, theorem proving, and continual learning.

4. Results and Illustration

The paper does not present large-scale empirical benchmarks but provides a closed-form 2-dimensional synthetic example to verify the internal consistency of the dynamics and the order-gap formula.

• Setup: A state vector $(c, u)$ representing confidence and uncertainty, with analytically defined expansion and consolidation operators.
• Observation: The order-gap $\Omega$ is shown to be large when confidence is low and uncertainty is high (regimes where new evidence matters) and vanishes as confidence approaches 1 or uncertainty is exhausted.
• Trajectory: A simulated run with five evidence items demonstrates that the windowed order-gap correctly identifies when pertinent evidence has been processed and when the system has settled, allowing for early stopping compared to a fixed budget.
• Coverage Check: The example illustrates a failure mode where the order-gap remains near zero not because the system converged, but because the evidence distribution failed to cover critical open questions (violating the non-degeneracy condition).

5. Significance and Scope

The paper claims to provide the first unified framework that treats state representation and termination as explicit, coupled design choices in recursive reasoning.

• Local vs. Global: The authors are explicit that the non-degeneracy theorem is a local condition near the fixed point. It does not guarantee global convergence or bound the error of the final answer. Global convergence guarantees are noted as requiring additional assumptions (Lipschitz constants, noise bounds) to be developed in future work.
• Practical Impact: The framework offers a mechanism to replace arbitrary stopping rules with a signal derived from the system's own trajectory. It suggests that by making the state explicit and measuring operator non-commutativity, systems can avoid redundant computation and detect when further refinement is futile or harmful.
• Future Directions: The paper outlines immediate extensions, including connecting the non-degeneracy condition to answer error via concentration arguments and empirical evaluation on long-context QA benchmarks.

In summary, the paper proposes that recursive reasoning systems must move from implicit, text-based states to explicit, graph-based epistemic states, and from fixed-budget termination to dynamic, order-gap-based stopping criteria to achieve robust and efficient inference.