A Formal Framework Enabling Cost-Efficient Semantic Code Transformation through Hybrid Deterministic-Probabilistic Processing

Abstract

Large Language Models (LLMs) demonstrate impressive reasoning capabilities but lack persistent, structured external memory. Existing agent paradigms (ReAct, Tree-of-Thoughts, Plan-and-Execute) encode world state implicitly within context windows, causing O(n²) context growth, state drift, and architectural unsuitability for large-scale semantic tasks.

We introduce External Semantic Memory Architecture (ESMA), a formal framework where world state is externalized into typed, hierarchical state machines with semantic namespaces. Under ESMA, snapshots encode state in structured paths (data.*, state.*, derived.*, meta.*), intents are reified as effect descriptors enabling replay and composition, and LLMs act as pure policy functions π: P_ai(s) → i without maintaining internal state history.

ESMA employs a hybrid architecture combining deterministic AST parsing with targeted LLM semantic interpretation. By decomposing schema extraction into structural extraction (deterministic, $0 cost) and semantic enhancement (GPT-4o-mini, $0.08), we achieve near-human-quality results with minimal model requirements.

We validate ESMA through @manifesto-ai/react-migrate, a production-grade code migration agent processing a 32-file SaaS application:

• 11 valid domain schemas with 196 entities and 56 intents (100% validity)
• 8 minutes processing time at $0.08 total cost (GPT-4o-mini)
• 375-500× cost reduction vs. theoretical ReAct/ToT/P&E implementations
• Ablation study: LLM integration provides +48% entities and +98% intents vs. heuristic-only baseline, with +10.6pp confidence improvement (80% → 90.6%)
• Model selection: Task decomposition enables GPT-4o-mini to achieve 90.6% confidence—16× more cost-effective than GPT-4 for structured interpretation tasks

ESMA resolves fundamental limitations of prior agent architectures (context explosion, implicit state, non-determinism, validation absence) and demonstrates that structured state externalization enables efficient LLM use with minimal models.

Keywords: Large Language Models, Multi-Agent Systems, State Machines, Semantic Memory, Program Synthesis, Hybrid Architecture

1. Introduction

1.1 The Memory Crisis in LLM Agents

Modern LLM agents operate by iteratively consuming state descriptions in natural language and producing action sequences. This paradigm has achieved success in interactive tasks like web navigation [1,2,3], but suffers from fundamental architectural limitations when applied to large-scale semantic tasks:

P1: Implicit State Representation

State exists only in the context window. For tasks spanning N entities, agents must maintain history by repeatedly including prior observations. This produces O(N²) token growth.

P2: Non-Deterministic Execution

Identical state descriptions can yield different actions due to sampling variance, prompt position effects, and attention instabilities. This makes debugging, testing, and auditing extremely difficult.

P3: Constraint Forgetting

Domain rules (type constraints, referential integrity, business logic) must be re-stated at every step. Long-horizon tasks inevitably violate constraints as context becomes diluted.

P4: Architectural Mismatch

Existing paradigms (ReAct [1], Tree-of-Thoughts [4], Plan-and-Execute [5]) were designed for small-state, sequential tasks. They lack mechanisms for persistent structured state, formal validation, or multi-agent coordination.

1.2 Quantifying the Failure: A Concrete Example

Consider extracting domain schemas from a 32-file React codebase containing 115 patterns (components, hooks, contexts, reducers).

ReAct Implementation:

Iteration 1: Read file1.tsx
  Context: "Found hooks: useAuth, useBilling, useProjects" (500 tokens)
Iteration 2: Read file2.tsx

Context: “File1: useAuth,useBilling,useProjects. File2: useAuth,useSettings”
(1,000 tokens)
Iteration 32: Summarize
Context: “File1: … File2: … File31: …” (16,000 tokens)
Total accumulation: 500×(1+2+…+32) = 264,000 tokens base
With refinement iterations (3-5×): 800k-1.3M tokens
Estimated cost (GPT-4): $36-40

Tree-of-Thoughts Implementation:

Explore domain clustering options for 11 candidates:
  Branch 1: All separate → evaluate (50k tokens)
  Branch 2: Merge auth+billing → evaluate (50k tokens)
  Branch 3-10: Other combinations → evaluate (400k tokens)
Total: 10 branches × 50k = 500k tokens
Estimated cost (GPT-4): $18-25
Problem: Which branch is “correct”? No ground truth.

Plan-and-Execute Implementation:

Plan → Execute → Discover new patterns → Replan → Execute → ...
Each replan: Reload full context (100k tokens)
Iterations: 5-10 replanning cycles
Total: 500k-1M tokens
Estimated cost (GPT-4): $30-40
Problem: Plans are static, discovery is dynamic.

Common Failures:

1. Context explosion: O(n²) growth
2. No structured state: Tracking in prose
3. No validation: Manual schema checking
4. Non-deterministic: Different runs → different outputs

1.3 Our Approach: External Semantic Memory

We propose ESMA, which restructures the agent-memory relationship through externalized, typed state machines:

Traditional Agent:              ESMA Agent:
┌─────────────────┐            ┌──────────────┐
│   LLM Agent     │            │   LLM (π)    │
│ ┌─────────────┐ │            │  Reasoner    │
│ │  History    │ │            └──────┬───────┘
│ │  Rules      │ │                   │ i = π(s)
│ │  State      │ │            ┌──────▼───────┐
│ │  Memory     │ │            │   Snapshot   │
│ └─────────────┘ │            │   s ∈ S      │
│   O(n²) cost    │            │   O(1) view  │
└─────────────────┘            ├──────────────┤
│    Schema    │
│   Σ (const)  │
└──────────────┘

ESMA Execution:

For each iteration t:
  1. Snapshot sₜ stores ALL state (structured)
  2. Projection Pₐᵢ(sₜ) extracts relevant view (constant size)
  3. LLM computes action: i = π(Pₐᵢ(sₜ))
  4. Transition: sₜ₊₁ = T(sₜ, i)
Token cost: O(n) not O(n²)
Context size: O(1) not O(t)
Validation: Automatic (schema constraints)
Determinism: Effect replay guarantees

For our 32-file task:

Total tokens: 325k (not cumulative)
Cost: $0.08 (GPT-4o-mini, not GPT-4)
Time: 8 minutes
Quality: 100% validity (formal validation)
Cost reduction: 375-500× vs. ReAct/ToT/P&E

1.4 Key Insight: Hybrid Architecture

ESMA achieves efficiency through task decomposition:

Stage 1: Deterministic Structural Extraction (SWC AST)
  - Parse TypeScript interfaces, reducer actions, contexts
  - Cost: $0, Time: 5 min
  - Output: 115 patterns, 31.4 entities/domain, 80% confidence
Stage 2: Probabilistic Semantic Interpretation (GPT-4o-mini)

Given: Structured patterns (not raw code)
Task: Map patterns → business entities/intents
Cost: $0.08, Time: +3 min
Output: 46.6 entities/domain (+48%), 90.6% confidence (+10.6pp)

Result: Near-human quality at minimal cost

Why mini model suffices:

• LLM sees structured input (200-500 tokens)
• Task is pattern matching, not complex reasoning
• Deterministic foundation guarantees correctness

1.5 Contributions

1. Formal model of semantic state machines with typed namespaces (data.*, state.*, derived.*, meta.*) and effect descriptors
2. Hybrid architecture combining deterministic parsing (fast, correct) with LLM interpretation (semantic, cheap)
3. Architectural solution to context explosion: O(1) projection vs. O(n²) accumulation
4. Production implementation processing 32-file codebases in 8 minutes at $0.08
5. Empirical validation:
   • 100% schema validity (11/11 valid)
   • 375-500× cost reduction vs. ReAct/ToT/P&E
   • Ablation study: +48% entities, +98% intents with LLM
   • Model selection: GPT-4o-mini achieves 90.6% confidence (16× cheaper than GPT-4)
6. Theoretical guarantees of determinism, safety, composability, bounded context

2. Formal Model

2.1 Schema: Immutable Domain Constitution

A schema Σ defines the invariant structure of a domain:

$$\Sigma = (E, F, C, D, I_{\text{valid}})$$

where:

• $E$: Entity type definitions
• $F: E \to \mathcal{F}$: Field specifications with types
• $C$: Constraint set (first-order logic)
• $D$: Dependency graph (DAG)
• $I_{\text{valid}}$: Valid intent types

Immutability: Schemas are constant at runtime. Changes require explicit versioning.

Example (Auth Domain):

Σ_auth = {
  E: { User, Session, Organization },
  F: {
    User: { id: string, email: string, orgId: string },
    Session: { id: string, userId: string, expiresAt: datetime }
  },
  C: {
    "User.email is unique",
    "Session.expiresAt > now()",
    "User.orgId ∈ Organization.id*"
  },
  I_valid: { login, logout, switchOrganization }
}

2.2 Semantic Snapshot: Hierarchical State

A snapshot encodes world state using semantic namespaces:

$$s = {\text{SemanticPath} \mapsto \text{Value}}$$

Well-Formedness:
$$S = {s \mid \forall c \in C, \, s \models c}$$

Example:

{
  "data.currentUser": { "id": "u123", "email": "alice@example.com" },
  "state.sessionId": "sess_abc",
  "state.isLoading": false,
  "derived.isAuthenticated": true,
  "meta.self.lastLoginAt": "2025-01-15T10:30:00Z",
  "meta.self.confidence": 0.95
}

2.3 Effect Descriptors: Reified Intents

Intents are reified as first-class Effect Descriptors:

interface EffectDescriptor {
  effect: string;                    // "domain:entity:verb"
  params: Record<string, unknown>;   // Typed parameters
  meta: {
    retryable: boolean;
    reversible: boolean;
    idempotent: boolean;
  };
  effects: SemanticPath[];           // Modified paths
  emits?: Channel[];                 // Triggered events
}

Properties:

• Determinism: Same snapshot + effect → same result
• Replay: Effect logs reconstruct state
• Composition: Effects chain into workflows
• Reversal: Inverse operations when reversible

Example:

{
  effect: "auth:session:login",
  params: { email: "alice@example.com", password: "***" },
  meta: { retryable: true, reversible: true, idempotent: false },
  effects: ["data.currentUser", "state.sessionId", "derived.isAuthenticated"],
  emits: ["auth:login:success"]
}

2.4 Transition Function

$$T: S \times \text{EffectDescriptor} \to S \times \text{Log}$$

Determinism Theorem:
$$\forall s \in S, e \in E: \, T(s, e) = T(s, e)$$

Safety Theorem:
$$\forall s \in S, e \in I_{\text{valid}}: \, T(s, e) = (s', \log) \implies s' \in S$$

Transitions preserve schema constraints.

2.5 AI Projection: Bounded LLM View

$$P_{\text{ai}}: S \to V_{\text{ai}}$$

Critical Property:
$$\forall t: |P_{\text{ai}}(s_t)| = O(1)$$

Projection size is constant, preventing context explosion.

Example Projection:

# State
user: alice@example.com
organizations: [Acme Corp, Beta Inc]
session_status: active
# Actions
- logout()
- switchOrganization(org_id: string)
# Metadata
confidence: 0.95
context_usage: 23%

2.6 LLM as Pure Policy

$$\pi: P_{\text{ai}}(s) \to i$$

The LLM does NOT maintain:

• Long-term memory
• Task history
• State tracking

All state is externalized.

Token Cost:
| Approach | Context/Step | Total |
|----------|--------------|-------|
| ReAct | O(t) | O(t²) |
| ESMA | O(1) | O(t) |

For t=32: ReAct ≈ 1000× more tokens.

3. Hybrid Architecture

3.1 Decomposition: Deterministic + Probabilistic

ESMA decomposes schema extraction into two stages:

Stage 1: Structural Extraction (Deterministic)

Use SWC AST parser to extract:

• TypeScript interface definitions
• Reducer action types
• Context API patterns
• Import/export dependencies

Properties:

• Deterministic: Same code → same AST
• Fast: 32 files in ~5 minutes
• Complete: Captures all syntax

Stage 2: Semantic Interpretation (Probabilistic)

Use GPT-4o-mini to interpret structures:

const prompt = `
Given TypeScript patterns:
Interfaces:

User: { id, email, name, organizationId }
Session: { id, userId, expiresAt }

Actions:

“auth/login”, “auth/logout”, “auth/switchOrganization”

Context Methods:

login(email, password)
logout()
switchOrganization(orgId)

Identify:

Business entities (with semantic descriptions)
Domain intents (with effect descriptions)

Output JSON.
`;

Stage 3: Merge & Validate

const entities = mergeEntities(
  heuristicEntities,    // From AST
  llmEntities,          // From LLM
  {
    preferLLM: true,            // Richer semantics
    validateStructure: true     // Must match AST
  }
);

3.2 Why This Decomposition Works

1. LLM sees structured input, not raw code

• AST → JSON (200-500 tokens)
• vs. raw code (2000-5000 tokens)
• Token reduction: 10×

2. LLM does pattern matching, not complex reasoning

• Task: "Map patterns → business concepts"
• Required: Pattern recognition + JSON formatting
• GPT-4o-mini suffices

3. Deterministic foundation + probabilistic enhancement

• AST guarantees structural correctness
• LLM adds semantic richness
• Best of both worlds

Cost-Quality Tradeoff:

vs. "LLM reads code" approach: $2-5, unknown quality.

3.3 Domain Hierarchy

$$\Gamma = (D, H, E)$$

where:

• $D$: Set of domains
• $H$: Hierarchy relation
• $E$: Event channels

Isolation Property:
$$\forall d_i, d_j \in D: d_i \neq d_j \implies s_i \cap s_j = \emptyset$$

Example:

orchestrator
  ├─ analyzer (AST parsing)
  ├─ summarizer (clustering)
  └─ transformer (schema generation)

3.4 Event Channels

$$\text{Channel} = (\text{name}, \text{PayloadSchema})$$

Example:

"analyzer:complete": { 
  payload: { domainsFound: number, confidence: number }
}

3.5 Metacognition

"meta.self.attempts": 2,
"meta.self.currentModel": "gpt-4o-mini",
"meta.self.confidence": 0.82

Enables:

• Self-correction
• Model upgrading
• Resource monitoring

4. Case Study: @manifesto-ai/react-migrate

4.1 System Overview

Production-grade tool for automatic schema extraction from React codebases.

Input: React (JSX/TSX, hooks, contexts, reducers)

Output: Manifesto domain schemas (.domain.json)

Technology:

• Runtime: Node.js 18+, TypeScript 5.x
• Parser: SWC (Rust, 20× faster than Babel)
• LLM: OpenAI GPT-4o-mini
• Storage: SQLite (effect logs for replay)

4.2 Pipeline Architecture

┌──────────────────────────────────────┐
│   Orchestrator Domain                │
│   (Pipeline Coordination)            │
└─────────┬────────────────────────────┘
          │
    ┌─────┴─────┬─────────┬──────────┐
    │           │         │          │
┌───▼────┐ ┌───▼──────┐ ┌▼─────────┐
│Analyzer│ │Summarizer│ │Transform │
│  AST   │ │Clustering│ │  Schema  │
└────────┘ └──────────┘ └──────────┘

Analyzer: Parse files, detect patterns

Summarizer: Cluster domains, identify boundaries

Transformer: Generate schemas, extract entities

4.3 Experimental Results

Dataset: Production SaaS application

• 32 files (~8,000 lines TypeScript/JSX)
• Features: Auth, Billing, Projects, Team, Notifications, Analytics, Settings

Processing Metrics:

Generated Domains:

Average: 17.8 entities/domain, 5.1 intents/domain

4.4 Example: Auth Domain Schema

Source Files:

• src/contexts/AuthContext.tsx
• src/hooks/useAuth.ts
• src/providers/AuthProvider.tsx

Generated Schema:

{
  "name": "auth",
  "version": "1.0.0",
  "description": "User authentication and session management",
“entities”: {
“User”: {
“type”: “object”,
“properties”: {
“id”: { “type”: “string” },
“email”: { “type”: “string”, “format”: “email” },
“name”: { “type”: “string” },
“organizationId”: { “type”: “string” }
}
},
“Session”: {
“type”: “object”,
“properties”: {
“id”: { “type”: “string” },
“userId”: { “type”: “string” },
“expiresAt”: { “type”: “string”, “format”: “date-time” }
}
}
},
“state”: {
“data.currentUser”: { “$ref”: “#/entities/User”, “nullable”: true },
“state.isLoading”: { “type”: “boolean” },
“derived.isAuthenticated”: { “type”: “boolean” }
},
“intents”: {
“login”: {
“effect”: “auth:session:login”,
“params”: {
“email”: { “type”: “string” },
“password”: { “type”: “string” }
},
“effects”: [“data.currentUser”, “state.sessionId”]
},
“logout”: {
“effect”: “auth:session:logout”,
“params”: {},
“effects”: [“data.currentUser”, “state.sessionId”]
}
}
}

4.5 Ablation Study: LLM Contribution

To quantify LLM's contribution, we compared:

Configuration A: Heuristic-only (No LLM)

• Method: AST + pattern matching rules
• Cost: $0, Time: 5 min

Configuration B: Heuristic + GPT-4o-mini

• Method: AST + heuristics + LLM interpretation
• Cost: $0.08, Time: 8 min

Results:

Improvements:

• Entities: +48% (31.4 → 46.6)
• Intents: +98% (11.2 → 22.2)
• Confidence: +10.6pp (80% → 90.6%)

Analysis:

Why does LLM find more entities?

Heuristics capture only explicit TypeScript types. LLM additionally discovers:

1. Implicit entities: NotificationsContextValue inferred from Context API usage
2. Relationship entities: UserOrganization from foreign key references
3. Business concepts: Subscription, Invoice in billing domain

Why does LLM find more intents?

Heuristics match literal action types. LLM discovers:

1. State machine patterns: login → loginStart, loginSuccess, loginFailure
2. CRUD operations: ADD_MEMBER, UPDATE_MEMBER, REMOVE_MEMBER
3. Composite actions: switchOrganization → logout + login + fetchOrgData

Projects domain exception:

Projects showed 0% entity improvement (comprehensive TypeScript types), but 100% intent improvement (16 → 32). This validates LLM value even with well-typed code.

4.6 Model Selection: Why GPT-4o-mini Suffices

Hypothesis: Task decomposition enables using weaker models.

Experiment: Compare GPT-4o-mini vs. theoretical GPT-4.

LLM Input (Already Structured):

{
  "interfaces": [
    { "name": "User", "fields": ["id", "email", "name"] }
  ],
  "actions": ["LOGIN", "LOGOUT"],
  "context": { "methods": ["login", "logout"] }
}

LLM Task: "Map patterns → business entities"

This is pattern recognition, not complex reasoning.

GPT-4o-mini capabilities sufficient:

• JSON parsing/generation ✓
• Pattern matching ✓
• Basic semantic understanding ✓

GPT-4 additional capabilities NOT needed:

• Multi-step reasoning ✗
• Extensive world knowledge ✗
• Long context understanding ✗

Cost-Effectiveness:

GPT-4o-mini is 16× more cost-effective.

General Principle:

If task = parse(input) + interpret(structures):
  Use mini model for interpretation
If task = complex_reasoning(raw_input):
May need larger model

5. Why Existing Architectures Fail

5.1 ReAct: Context Explosion

ReAct [1] interleaves reasoning and acting.

For 32-file task:

Iteration 1:  500 tokens
Iteration 2:  1,000 tokens (cumulative)
Iteration 3:  1,500 tokens
...
Iteration 32: 16,000 tokens
Total: 264,000 tokens base
With refinement: 800k-1.3M tokens
Cost (GPT-4): $36-40

Failure Modes:

• Context limit exceeded
• Earlier files "forgotten"
• No structured validation

5.2 Tree-of-Thoughts: Combinatorial Explosion

ToT [4] explores multiple paths.

For 11 domain clustering:

Branch 1: All separate (50k tokens)
Branch 2: Merge auth+billing (50k tokens)
...
Branch 10: Other combinations (50k tokens)
Total: 10 × 50k = 500k tokens
Cost (GPT-4): $18-25

Failure Modes:

• Which branch is "correct"?
• No evaluation function
• Redundant computation

5.3 Plan-and-Execute: Frequent Re-planning

P&E [5] generates and executes plans.

For dynamic discovery:

Plan → Execute → Discover → Replan → ...
Each replan: 100k tokens
Iterations: 5-10 cycles
Total: 500k-1M tokens
Cost (GPT-4): $30-40

Failure Mode: Plans are static, discovery is dynamic.

5.4 Comparative Analysis

Cost Reduction:

• vs. ReAct: 450-500×
• vs. ToT: 225-312×
• vs. P&E: 375-500×

Average: 375-437× cheaper

Architectural Comparison: