Reasoning Circuit Complexity

Assumptions

Formal definitions for this appendix are given in B.2. The assumptions beneath the analysis are:

B.1 — Theoretical lineage

Reasoning graphs are not a novel mathematical object. They are a specific application of a well-studied structure: the directed acyclic graph (DAG) with typed nodes, data-dependent edges, and optional iteration (which, when unrolled, produces a deeper DAG). The relevant theoretical traditions are:

Circuit complexity (1940s–present). Boolean circuits are DAGs where nodes are logic gates and the two primary measures are size (total gates) and depth (longest path from input to output). Circuit complexity proved that certain functions require certain depths regardless of circuit width — the foundational depth separation results. The key insight for cognitive engineering: depth and size define a hierarchy of computational power, and some problems cannot be solved at insufficient depth no matter how many gates you add.

Dataflow graph theory (1960s–present). Dataflow programs are DAGs where nodes are operations and edges are data paths. Execution is asynchronous: a node fires when all its inputs are available. Dataflow theory provides the execution semantics for reasoning graphs — nodes execute when dependencies are satisfied, tokens flow through edges, and the graph’s topological structure determines what can be parallelized.

Algorithmic complexity (Big-O, 1960s–present). Standard complexity analysis characterizes how costs scale with input size. For reasoning graphs, the natural scaling variables are iteration count, evidence size, and claim count. Big-O analysis applies directly once we define the cost model.

What this appendix adds is the application of these frameworks to reasoning graphs specifically — treating LLM calls as stochastic gates with measurable costs (A1), and analyzing the structural properties of graphs built from reasoning primitives.

B.2 — Formal definitions

Reasoning graph

A reasoning graph G = (V, E, τ, σ) where V is a set of nodes, E ⊆ V × V is a set of directed edges (data dependencies), τ: V → {GEN, RET, VRF, EVL, REV, SYN, BRN, LOP, SIM, OBS} assigns each node a primitive type, and σ: V → PromptSet assigns each node a prompt configuration. Edges represent data flow: if (u, v) ∈ E, then v requires the output of u as input.

Structural measures

Unrolled DAG

A reasoning graph with iteration (LOP nodes) can be analyzed as a DAG by unrolling: replacing the loop with I sequential copies of the loop body, where I is the iteration budget. The unrolled graph G′ has depth D(G′) = D_pre + I × D_loop, where D_pre is the pre-loop depth and D_loop is the depth of one iteration. This is the worst-case DAG. Best-case depth occurs when convergence is reached on the first iteration: D_pre + D_loop.

B.3 — Cost model

Each node in a reasoning graph has a measurable execution cost. We define a per-node cost function and aggregate it to produce graph-level metrics.

The model multiplier m_v accounts for different model sizes and prices at different nodes — e.g., a small model for fact-checking, a large model for generation. Tool cost t_v covers retrieval calls, web search, database queries, and external API calls.

Total cost for a run executing node set V′ (the actually-executed subset, which may be less than V if convergence occurs early):

Latency is the wall-clock critical path. Let S₁, S₂, …, S_D be the topological layers of the (unrolled) graph:

This is where width matters. Parallel nodes in the same layer contribute only the maximum latency of the layer, not the sum. A graph with width 2 at a given layer pays the cost of the slower node, not both nodes.

Token scaling

Token cost per iteration is not constant. Later iterations include richer context because the evaluation from prior iterations feeds into the strategy node. The key scaling variable is not the iteration index but the claim count — the number of specific assertions, corrections, and evaluation findings that accumulate across iterations.

Let C_i be the claim count at iteration i. The prompt tokens for the strategy node at iteration i scale as:

If claim count grows linearly with iterations (each iteration discovers a roughly constant number of new issues), total token cost is O(I²). If claim count stabilizes (later iterations discover fewer issues because earlier ones resolved them), total token cost approaches O(I). The shape of claim count growth is an empirical question whose answer determines whether context compression is worth the additional node cost.

Actionable implication: if empirical measurement shows C_i growing linearly, add a ContextCompressor node between iterations to reduce claim tables to only unresolved items. If C_i stabilizes naturally (because issues get fixed), compression adds cost without benefit. Measure before optimizing.

B.4 — Topology classification

Reasoning graphs can be classified into complexity classes by their structural properties, analogous to the circuit complexity hierarchy (AC⁰, TC⁰, NC¹, etc.). We propose five classes based on observed topologies in practice. In the columns below, n is the number of nodes — the reasoning steps in the graph — and I is the iteration budget, the maximum number of times a convergence loop may repeat.

VRF and EVL are the two checking primitives a graph can contain. A Verify (VRF) node re-checks a draft against its original inputs — did we actually answer the question, are the cited facts right? An Evaluate (EVL) node judges quality or weighs competing options — how good is this, which alternative wins? Verification density (ν) is simply the share of a graph’s nodes that are one of these two; a graph with none, like G₁ and G₂, is doing no checking at all, which is why its ν is 0.

By construction, each class subsumes the one below it. G₂ can express everything G₁ can (by using a single node). G₃ adds verification. G₄ adds iteration. G₅ adds parallelism with convergent synthesis. The hypothesis — and it is a hypothesis (A4) — is that each increase in class produces measurable improvements in output quality for tasks of sufficient complexity, and that for some tasks, lower classes cannot achieve a target quality threshold regardless of model capability.

B.5 — Worked example: the Arcus baseline graph

The graph below is a reduced, representative form of the Arcus baseline — the production Reg E adjudication graph — trimmed to a handful of nodes so the structural measures are easy to trace. The production graph follows the same G₄ shape at larger scale; a live dossier’s integrity seal records fourteen sealed model calls. It is written in Reason, the language these graphs are authored in, and we analyze it with the framework defined above.

graph answer_question {                 // G₄ · reduced form; node bodies abridged

  node clarify:gen {                     // OBS role
    input: query
    output: clarification
    prompt_set: clarify
  }

  node strategy:gen {                    // GEN
    input: query, clarification, iteration
    output: strategyResult
    prompt_set: strategy
  }

  node draft:gen {                       // GEN
    input: query, strategyResult
    output: draftResult
    prompt_set: draft
  }

  node factCheck:ass {                   // VRF role
    input: draftResult
    output: factCheckResult
    prompt_set: factCheck
  }

  node impact:ass {                      // SIM role
    input: draftResult, factCheckResult
    output: impactResult
    prompt_set: impact
  }

  node strategyEval:ass {                 // EVL role
    input: draftResult, impactResult
    output: judgmentArtifact
    prompt_set: assessor
  }

  gate convergence {                    // EVL role · the loop
    input: judgmentArtifact
    mode: iteration
    max_iterations: 3
    routes: {
      iterate -> strategy          // loop back
      accept  -> exit
      fail    -> exit
    }
  }

  node exit:act {
    input: judgmentArtifact
    output: finalResponse
    action_type: legacy_node
    target: exit
  }
}

A note on two vocabularies (A + C). This appendix classifies each node by an analytic primitive — GEN, VRF, EVL, SIM, RET — chosen so that structural measures like verification density are easy to define. The Reason language tags each node by a smaller set of operations, seen above as :gen, :ass, :crt, :arb, :act. The two do not line up one-to-one: a single :ass node plays whatever checking role the analysis calls VRF or EVL, and the impact node reasons in a SIM (simulation) role though it is authored :ass. The mapping:

Verification density (ν) counts the analytic VRF and EVL nodes — authored here as :ass and :crt. The distinction the analysis draws (verify vs. evaluate vs. simulate) is finer than the language needs to execute, which is why several analytic primitives collapse onto :ass. Production node bodies also carry a schema; it is omitted above for brevity.

Structural analysis

Complexity analysis

Node complexity: O(I · K) where I = iteration count and K = 6 nodes per iteration. Linear in iterations. Each additional iteration adds exactly 6 LLM calls. The constant factor (6) is the iteration unit cost.

Token complexity: O(I · K · t + I² · b · C) where t is average per-node token cost, b is per-claim marginal prompt cost, and C is claims-per-iteration growth rate. The first term is linear (base cost). The second term is quadratic only if claim count grows linearly. If claims stabilize (the common case when the graph is working correctly), effective token complexity approaches O(I).

Latency: O(I · K) because width = 1. No parallelization available. Latency equals total node count. Every node is on the critical path.

Comparison across topology classes

The following table compares the baseline G₄ graph to simpler topologies on the same task, assuming identical model (R) and knowledge (K):

The structural insight: moving from G₁ to G₄ multiplies LLM calls by 13× but adds verification density of 0.50, iteration with learning transfer, and strategy-level evaluation. If EIE score improves by more than the proportional cost increase, the graph design is the higher-ROI investment. Preliminary observations suggest EIE improvements of 60–80% for a 13× cost increase — a quality/cost ratio that would be considered excellent in any engineering domain.

B.6 — The quality/cost objective

Graph comparison requires an objective function. We define two standard optimization formulations:

Efficiency maximization: max Q / Cost(G). Find the graph that produces the highest quality per unit cost. This is the standard formulation for resource-constrained environments where budget is fixed and quality must be maximized within it.

Threshold satisfaction: min Cost(G) subject to Q ≥ τ. Find the cheapest graph that achieves a target quality level. This is the standard formulation for regulated environments where a quality floor is mandated and the question is how to reach it at minimum cost.

With these formulations, graph comparison becomes precise:

Graph A dominates Graph B if A achieves ≥ Q at ≤ Cost. Dominance is objective and testable.

The Pareto frontier is the set of graphs where no improvement in Q is possible without increasing Cost. Graphs on the frontier are optimal for their cost level. Graphs below the frontier are suboptimal and should be redesigned.

Graph topology shifts the frontier. If G₄-class graphs produce a higher Pareto frontier than G₃-class graphs across a range of tasks, then the structural complexity of G₄ is justified — the additional verification and iteration nodes produce quality improvements that exceed their cost.

B.7 — Information transfer between iterations

The Arcus baseline graph discards the draft between iterations and carries forward only the evaluation findings. We treat this as a deliberate bandwidth control technique rather than an incidental choice, with the properties below:

The narrow-bandwidth design trades higher per-iteration token cost for higher quality ceiling and lower error propagation. Each iteration is an independent sample from an improved strategy, not a patch on a potentially flawed artifact. This is the reasoning-graph equivalent of the distinction between policy gradient methods (resample from updated policy) and value patching (modify the existing trajectory) in reinforcement learning.

B.8 — The primitive basis set: open questions

Circuit complexity begins with a basis set of gates (AND, OR, NOT) and asks two foundational questions: is the set complete (can it express all computable Boolean functions) and is it minimal (is any gate redundant)? The same questions apply to the Reason primitive set.

The current basis: GEN, RET, VRF, EVL, REV, SYN, BRN, LOP, SIM, OBS.

Completeness. Can every useful reasoning topology be expressed as a composition of these ten primitives? Preliminary evidence suggests yes — every graph we have designed across credit underwriting, insurance governance, AML/KYC, and general question-answering has been expressible using only these primitives. But absence of a counterexample is not a proof. A formal completeness argument would require defining the class of ‘useful reasoning topologies’ precisely, which is itself an open problem.

Minimality. Can any primitive be expressed as a composition of others? Candidates for reduction:

REV (Revise) may be expressible as GEN conditioned on EVL output. If every revision is just a constrained generation informed by evaluation feedback, REV is syntactic sugar for GEN + EVL, not a true primitive.

SYN (Synthesize) may be expressible as GEN with multiple inputs. If synthesis is just generation from a merged input set, it reduces to GEN.

OBS (Observe) may be expressible as EVL applied to the graph’s own trace. If meta-cognitive monitoring is just evaluation of the reasoning process rather than the reasoning content, it reduces to EVL + trace access.

If REV, SYN, and OBS reduce, the minimal basis might be 7 primitives: GEN, RET, VRF, EVL, BRN, LOP, SIM. Whether this reduction affects expressiveness or merely notation is an open research question.

B.9 — Open theoretical questions

This appendix establishes a measurement framework and a classification hierarchy. Several foundational questions remain open:

Depth separation. Do there exist tasks where G₃-class graphs cannot achieve EIE ≥ τ regardless of R, but G₄-class graphs can? A positive result would be the founding theorem of cognitive engineering — proof that reasoning quality has structural complexity classes.

Verification density threshold. Is there a minimum verification density below which output integrity degrades regardless of model capability? If ν < 0.2 produces unreliable outputs for all R, that’s not a design guideline — it’s a structural law.

Optimal bandwidth. Under what conditions does wide-bandwidth (draft-preserving) iteration outperform narrow-bandwidth (eval-only) iteration? The answer likely depends on the ratio of strategy failures to execution failures.

Basis completeness and minimality. Is the 10-primitive basis complete and minimal? What is the true minimal basis for reasoning graphs?

Graph equivalence. When do two structurally different graphs produce equivalent output distributions? Defining graph equivalence for reasoning (not just computation) requires a quality-aware equivalence relation.

Cost-quality frontier universality. Is the Pareto frontier between cost and quality consistent across tasks, or task-specific? If universal patterns emerge (e.g., verification density ≥ 0.3 is always on the frontier), those patterns become design laws.