# A Self-Improving Agent that Grows its Own DSL: Oracle-Free Operator Induction for Exact Question Answering

> A frozen LLM grows its own verifiable DSL without any oracle, tripling answerable questions and inducing sound operators via differential testing and metamorphic conservation laws.

- **Source:** [arXiv](https://arxiv.org/abs/2610.20809)
- **Published:** 2026-10-17
- **Permalink:** https://picx.dev/p/TtkQzi
- **Whiteboard:** https://picx.dev/p/TtkQzi/image

## Summary

# A Self-Improving Agent that Grows its Own DSL: Oracle-Free Operator Induction for Exact Question Answering

## Summary (Overview)

- **Core contribution**: The paper presents a two-loop, single-model system where a frozen LLM grows its own domain-specific language (DSL) to answer exact question-answering tasks—without any reward signal, judge model, or ground-truth answer key.
- **Key innovation**: An oracle-free admission gate for new operators that requires (1) two independently written implementations to agree on every record (differential testing) and (2) satisfaction of conservation laws (metamorphic relations) stated over already-trusted operators.
- **Empirical results**: The inner loop roughly triples coverage of answerable questions; the outer loop self-extends on disjoint starting sets, inventing operators outside the starting closure. The admission rule rejects 138/138 buggy operator variants, whereas admit-if-it-runs, self-consistency, and compression signals admit most.
- **Generalization**: The mechanism transfers unmodified to two further domains (business-ledger and clinical-encounter QA), growing answerable sets more than tenfold and nearly twentyfold, and stays sound across four model families.
- **Key limitation**: The most-requested capability—a mode reducer (most-frequent-value)—is permanently out of reach because it has no conservation law.

---

## Introduction and Theoretical Foundation

### Background and Motivation

The paper addresses a fundamental problem in self-improving agents: **how can an agent expand what it can compute without any teacher signal, while keeping every answer exactly checkable?**

Standard self-improvement approaches rely on:
- **Reward signals** (e.g., FunSearch, AlphaEvolve)
- **Judge models** (LLM-as-judge)
- **Compression signals** (library learning like DreamCoder, LILO, TroVE)

However, when answers must be *exactly right* (e.g., "how much did my top buyer spend?"), these signals are insufficient—a wrong skill can score well, satisfy a judge, and compress the library as neatly as a correct one.

### Theoretical Foundation

The paper builds on **program-of-thoughts (PoT)** methods, where the model writes a program instead of doing arithmetic in its head. The program is an expression in a small sandboxed DSL:

- A fixed operator set $O$ answers exactly the questions expressible by composing its operators—its **closure** $\text{cl}(O)$.
- The agent must **grow its own DSL**, adding operators its questions demand, without ever admitting one it cannot verify.

**Key notation**:
- For an expression $e$, $\sigma(e)$ denotes the **value signature**—the vector of $e$'s values across validation records $M$.
- Two expressions with equal signatures compute the same quantity on $M$.
- An operator set $O$ answers a question when some expression over $O$ matches the question's value signature.

### The Admission Rule

An operator is admitted only on evidence requiring **no answer key and no judge**:
1. **Differential testing**: The model writes the operator twice, independently; the two implementations must agree on every record.
2. **Metamorphic relations**: Conservation laws stated over already-trusted operators (e.g., per-group totals sum to the global total: $\text{sum}(\text{op}(\text{keys}, \text{amounts})) = \text{sum}(\text{amounts})$).

This rule is **oracle-free but empirical**, not formal proof: agreement is checked on a finite validation set within tolerance $10^{-6}$, and conservation laws are the ones the model states.

---

## Methodology

### The Two Nested Loops

Both loops are run by a **single frozen model** with no fine-tuning, no ground-truth oracle, and no judge.

#### Inner Loop: Expanding Coverage Within a Fixed Operator Set

Four stages (Algorithm 1, `INNER_LOOP`):

1. **Propose**: Shown example (question, expression) pairs, the model invents new natural questions answerable by one expression over the same data.
2. **Execute**: Each expression is evaluated on every validation record under a sandboxed interpreter exposing only current operators.
3. **Verify**: The model answers the question text *alone*, separately; the proposal is kept only if this independently written expression matches the first on every record.
4. **Keep if new**: A verified quantity counts only if its value signature differs from all starting types and previously accepted quantities.

#### Outer Loop: Inducing New Operators

Four steps (Algorithm 1, `OUTER_LOOP`):
1. **Discover the gap**: Tally which missing capability questions most demand; author an operator.
2. **Validate** with no ground-truth answer (the gate).
3. **Re-run** the inner loop with the enlarged operator set.
4. **Report**.

The gate checks:
1. **Two implementations agree** (differential testing, relative tolerance $10^{-6}$).
2. **Conservation and structure hold** (metamorphic relations over trusted operators).
3. **Answers hold up downstream**: every question the operator unlocks must pass the inner loop's independent-agreement check.

**Algorithm 1 (Pseudocode)**:
```
procedure INNER_LOOP(starting question types T, operators O, records M)
    K ← {SIG(t, M) : t ∈ T}  ▷ quantities already answerable
    repeat
        for each (q, e) the model proposes as a (question, expression) pair using only O do
            s ← EVALUATE(e, M)  ▷ skip if e uses an operator ∉ O or is not a single number
            E′ ← ANSWER_FROM_QUESTION(q)  ▷ expressions written from the question text alone
            if some e′ ∈ E′ has SIG(e′, M) = s and s ∉ K then
                add s to K; record the question type (q, e)  ▷ agreement + not seen before
            end if
        end for
    until a full pass adds nothing to K
    return the recorded question types
end procedure

procedure OUTER_LOOP(operators O, records M, a request outside the closure of O)
    (f, f′) ← INDUCE(missing capability)  ▷ model writes TWO independent implementations
    ok ← DIFFERENTIAL(f, f′, M) ∧ METAMORPHIC(f, M)  ▷ agree on every input; obey trusted relations
    if ok then
        return INNER_LOOP(starting types, O ∪ {f}, M)  ▷ admit; downstream round-trip re-checks each type
    else
        return reject f  ▷ admitting it would break exact verifiability
    end if
end procedure
```

### Sandbox and Substrate

- **Sandbox**: Expressions are parsed to an AST and evaluated by an interpreter allowing only whitelisted node types and bare, registered functions—no attribute access, no arbitrary call targets, no state.
- **Substrate**: The raw data representation and attribute-free, first-order sandbox for operator bodies remain fixed; the loop grows only the operator vocabulary.

---

## Empirical Validation / Results

### Setup

- **Base model**: Qwen3.6-35B-A3B (frozen, no fine-tuning, reasoning off, temperature 1.0)
- **Data**: Fully synthetic merchant transaction corpus (no real customer data); 63-merchant held-out validation set
- **Transfer domains**: BookSQL (business-ledger), EHRSQL (clinical encounters over MIMIC-III)

### 4.1 Inner Loop: Coverage Expansion

| Metric | Value |
|--------|-------|
| Starting types | 10 |
| Proposed candidates | 82 |
| Executed to single number | 40 |
| Passed independent-expression check | 35 |
| New verified quantities | 26 |
| **Answerable set after one round** | **10 → 36** |
| After subsequent rounds | 36 → 54 → 63 |

**Robustness**: Across 13 starting sets, every one yields +9 to +39 new verified types (mean +18.3).

### 4.2 Outer Loop: Automated Operator Induction

- Three disjoint starting sets each self-extend, admitting 2–6 distinct per-group operators with no oracle.
- The most-requested capability across all sets is **per-group aggregation** (e.g., `per_group_sum(keys, values)`).
- **Control**: A no-induction control answers *none* of the new questions, isolating induction as the cause.
- **Chained rounds**: With round-1 operators in the library, the model discovers further gaps (weighted-mode, equality, argmax) and induces more operators.

### 4.3 Gate Soundness: Mutation Study

**Table 1: Gate-component ablation on the mutation/adversarial pool** (14 operators, 138 buggy single-point mutants, 6 adversarial constructions; 63 merchants)

| Configuration | Threat model | Buggy | Adv. | False rej. |
|---|---|---|---|---|
| Compile-only (sandbox) | n/a | 129/138 | 6/6 | 0/14 |
| +differential | uncorrelated | **0/138** | 4/6 | 0/14 |
| +differential | correlated | 129/138 | 6/6 | 0/14 |
| +metamorphic | n/a | 10/138 | 5/6 | 1/14 |
| **Full gate** | **uncorrelated** | **0/138** | 4/6 | 1/14 |
| **Full gate** | **correlated** | **10/138** | 5/6 | 1/14 |

**Key findings**:
- With an independent reference, the false-admit rate is **0/138**.
- In the correlated worst-case (identical bug in both implementations), metamorphic checks still admit only 10/138.
- The reference need not be co-generated: a separate-call reference still admits 0/138, even from a different model family (Gemma-3-27B).
- No teacher-free signal substitutes for the gate: admit-if-it-runs and self-consistency each admit 129/138; compression admits 101/138.

### 4.4 Transfer Across Base Models

- **Gate stays sound at every scale**: No wrong operator admitted by any model (Qwen3 dense 4B/8B/14B/32B, Qwen3.6-35B-A3B).
- **Induction fires across the size range**, though not monotonically.
- **Cross-family transfer**: Mistral-Small-24B and Llama-3.3-70B both self-extend; Gemma-3-27B self-extends only on the timing seed (its expressions execute less often: median 13% vs 31%/34%).

### 4.5 Generalization Across Domains

| Domain | Seed types | Final types | Growth |
|--------|-----------|-------------|--------|
| Merchant (amounts/timing) | 10 | 336 | ~34× |
| BookSQL (business-ledger) | 15 | 162 | >10× |
| EHRSQL (clinical) | 13 | 248 | ~19× |

### 4.6 Human Validation

- 89% of DSL expressions judged faithful; 97% of questions well-formed.
- All 53 induced operators: annotators unanimously agreed the two independent implementations compute the same function.

---

## Theoretical and Practical Implications

### Theoretical Significance

1. **Oracle-free verification**: The paper demonstrates that exact self-improvement is possible without reward, judge, or answer key—challenging the assumption that these signals are necessary for skill acquisition.

2. **Complementary verification layers**: Differential testing catches independent mistakes; metamorphic conservation checks catch shared ones. Together they provide a sound admission gate.

3. **Capability gap discovery**: The frozen model can surface and rank the capabilities its own questions demand but its operators cannot express—a form of introspective gap-seeking.

4. **Domain and model transfer**: The mechanism is a property of the method, not of one schema or model family, evidenced by transfer across three domains and four model families.

### Practical Implications

1. **Safe self-improvement for exact tasks**: Useful for financial, clinical, and other domains where answers must be exactly right and errors are costly.

2. **Auditable libraries**: The sandbox keeps every induced operator composable over audited base operators in a language too small to escape to arbitrary computation.

3. **Verified compression**: The same discipline supports compression—folding recurring patterns into named operators only if equivalent on every record.

4. **Comparison to text-to-SQL**: The DSL is exact by construction, uniform across categories and models, and concise, whereas SQL is brittle and model/stack/prompt-sensitive on ordered and per-group queries.

---

## Conclusion

### Main Takeaways

The paper presents a two-loop, single-model system that grows its own DSL under an oracle-free admission rule:
- **Inner loop** roughly triples coverage of answerable questions within a fixed operator set.
- **Outer loop** invents operators verified with no answer key, using differential testing and metamorphic relations.
- The system transfers unmodified to two further domains and stays sound across four model families.

### Limitations

1. **Mode reducer permanently out of reach**: The most-requested capability (most-frequent-value) has no conservation law, so only the mode value (non-numeric argmax) stays outside the DSL.
2. **Scaling to many rounds untested**: Demonstrated up to three induction rounds per seed.
3. **Modest admission yield**: Most drafts rejected because the different-style reference reverts to sandbox-forbidden method calls (81% of rejections).
4. **Adversarial edge cases**: A conservation-preserving relabeling can pass harmlessly; a size-changing bug escapes if its witnessing relation names a bare builtin.
5. **Seed focus on per-group aggregation**: All three seeds center on per-group aggregation; a seed around a qualitatively unrelated gap is untested.

### Future Directions

- Robust stopping rules for the inner loop (returns diminish over rounds).
- Scaling to many induction rounds.
- Improving admission yield (reducing method-call revert rate).
- Testing seeds around qualitatively different capability gaps.
- Sandbox-level fixes for adversarial edge cases (e.g., keyed access simulation).

---

_Markdown view of https://picx.dev/p/TtkQzi, served by PicX — AI-generated visual whiteboard summaries of research papers._