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

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

Abstract

Figures & tables

LLM Agent Self-Improvement

A Relative-Computability Theory of Self-Improving Agents

Abstract

LLM Agent Self-Improvement

Explore similar work

Appendix

A Relative-Computability Theory of Self-Improving Agents

Skill∞^{\infty}∞: Recursive Self-Improvement for Agent Skill Optimization

Reliable Self-Improvement Training by Verifying Reasoning, Not Just Answers

Skill $^{\infty}$ : Recursive Self-Improvement for Agent Skill Optimization

Yun-Shiuan Chuang; Yirou Ge; Yixi Li; Yiming Bian; Zijie Pan; Jenna L. Ballard; Uma Kona; Linsey Pang

cs.AIOct 14, 2026

Authors: Yun-Shiuan Chuang, Yirou Ge, Yixi Li, Yiming Bian, Zijie Pan, Jenna L. Ballard, Uma Kona, Linsey Pang,

Organizations: PayPal AI

A self-improving agent has to decide which new skills to keep, and in practice it keeps whatever earns a high reward, convinces a judge model, or compresses its library, even when the skill is wrong. That is fine until the answers have to be exactly right: over a table of transactions, a total is either right or wrong. We ask a harder question: can an agent grow what it can compute with no reward, no judge, and no answer key, and still be exactly right? A single frozen model runs two nested loops over a small, exact domain-specific language (DSL). The inner loop answers new questions only when two independently written expressions agree on every record. The outer loop discovers its own missing capability and authors an operator for it, admitted only when an independent second implementation agrees and the result obeys a conservation law, all without ground truth. The inner loop roughly triples the answerable-question set, and the outer loop self-extends on disjoint starting sets, inventing operators outside the starting closure; a no-induction control answers none of the new questions. The admission rule is empirically sound: it rejects 138 of 138 buggy operator variants under an independent reference, even one written by a different model family, where the admit-if-it-runs, self-consistency, and compression signals the field relies on admit most of them. Unmodified, the same mechanism self-extends on two further domains with unrelated schemas, business-ledger and clinical-encounter question answering, growing their answerable sets more than tenfold and nearly twentyfold. The loop transfers across model families too: run with further proposers, the gate stays sound and independent families self-extend comparably, with only the induction yield tracking each proposer's DSL fluency.

Figure 1: The two nested loops, both run by a single frozen model with no ground-truth oracle and no judge. The inner loop (blue) expands the answerable set within a fixed operator set, keeping a question only when two independently written expressions agree on every record ( $\sigma(e_{1})=\sigma(e_{2})$ ). The outer loop (green) induces a new operator when a capability gap recurs, admits it through the oracle-free validation gate, and folds it into the library before re-running the inner loop. Detailed in Section 3 .

Panel of Figure 2 — Figure 2: One continuous closed-loop trajectory per domain. Shaded/unshaded bands are successive inner-loop phases; each dashed vertical line is an outer-loop induction ( $+n$ operators admitted); the solid line is cumulative answerable types and the dashed orange line the subset whose expression uses an induced operator. Two rounds grow the set $10\to 336$ (Merchant, amounts/timing seed), $15\to 162$ (BookSQL), and $13\to 248$ (EHRSQL) under the same namespace and gate. Discussed in § 4.2 and 4.5 .

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

Table 1: Gate-component ablation on the mutation/adversarial pool (14 operators, their 138 buggy single-point mutants, and 6 adversarial constructions; 63 merchants), each check toggled independently; the threat model is uncorrelated (independent reference) or correlated (reference carries the same bug). Buggy , Adv. , and False rej. count false-admits over the 138 mutants, admits of the 6 adversarial constructions, and wrongful rejections of the 14 correct operators.

Panel of Figure 3 — Figure 3: Base-model ablation: the same outer loop run with five base models per domain, in the stacked convention of Figure 2 (light: initial seed types; solid: additional types expressible with the seed operators; hatched: types needing an induced operator; label: operators admitted). 4B/8B/14B/32B are Qwen3 dense models and 35B is the Qwen3.6-35B-A3B main model. Read for gate soundness and whether induction fires, not as a cross-model coverage ranking (absolute coverage is volume-sensitive; § 4.4 , Appendix P ).

Panel of Figure 4 — Figure 4: Cross-family transfer: the same closed loop, same frozen prompt and gate, with four proposer families (Qwen3.6-35B-A3B, Mistral-Small-24B, Gemma-3-27B, Llama-3.3-70B) on the three domains, in the stacked convention of Figure 3 . The gate stays sound for every family (zero false admits throughout), and two further families self-extend (Mistral on Merchant and BookSQL, Llama on all three). Read for soundness and induction, not coverage ranking; per-family compile rates and the three-seed companion are in Table 11 (§ 4.4 ).

Appendix figures & tables16 assets

Supplementary material from the paper’s appendix.

Panel of Figure 5 — Figure 5: One continuous closed-loop trajectory per starting set, on a fixed validation set (63 merchants). Shaded and unshaded bands mark successive inner-loop phases; a dashed vertical line at each phase boundary is an outer-loop induction, labeled with the number of operators it admits ( $+n$ ). The inner loop climbs on its current operators (solid), an induction enlarges the library, and it climbs again. The capability each induction closes, in order, is: a most-common-value gap closed by a family of per-group aggregation and counting operators, then a related weighted-mode gap closed by more per-group counting operators (Amounts & Timing); a count gap closed by conditional-filter and per-group count/sum operators, then an equality gap closed by equality-filter and grouped-sum operators (Top Buyer); and a most-common-value gap closed by per-group counting operators, then an argmax gap closed by a single grouped-sum reducer (Timing). The orange dashed line counts only the answerable types whose expression calls an operator admitted this round : it is flat at zero through the first inner phase (no operator to use) and rises only after an induction, so the post-induction gains are genuinely induction-driven, not the inner loop continuing on the base operators. Of the newly answerable types in the first post-induction phase, $76/100$ (Amounts & Timing), $178/208$ (Top Buyer), and $35/120$ (Timing) call an induced operator; the cumulative counts after the second post-induction phase are $116$ , $254$ , and $53$ respectively. All three starting sets admit new operators at both inductions and keep climbing through a third inner phase; none self-limits within the two induction rounds tested here. Inner phases are capped at eight passes and are still rising at the cap, so these are lower bounds on each phase’s reachable set.

Appendix

Table 2: Inner-loop coverage growth on the amounts/timing starting set with a fixed operator set (diminishing returns; each round counts only types not found earlier). Columns: distinct (question, expression) pairs proposed , those executable to one number per record, those also verified by the independent-expression check, the new types, and the cumulative total . The ten seed types count in total but not new (§ 4.1 ).

Starting set	Init. ops	Gap	Admitted	Proposed	Executable	Verified	New	Using induced
Amounts/timing	9	mode	6	387	108	79	65	25
Top-buyer	8	where	5	590	140	81	62	6
Timing	15	mode	2	332	133	95	66	2
Amounts/timing (round 2)	15	mode	2	339	119	88	67	3
Control (amounts/timing, no induction)	9	n/a	0	277	103	92	69	0

Appendix

Table 3: Automated outer-loop induction on three independent starting sets, each from its own minimal operator set (63 validation merchants). Using induced counts new types whose expression calls an operator admitted this round; the control runs amounts/timing with induction skipped (Appendix F ).

Compressed operator	Sites	Questions	Chars saved	Equiv. checks
max(per_group_sum(a0, a1))	14	10	84	882
ratio(sum(a0), nunique(a1))	6	6	42	378
max(gaps_days(a0))	4	4	8	252
min(gaps_days(a0))	4	4	8	252
mean(gaps_days(a0))	4	4	12	252

Appendix

Table 4: Verified compression: the most-reused sub-expression patterns among the 219 verified expressions are folded into named operators, each admitted only if equivalent to the pattern it replaces on every record (63 merchants). Sites is occurrences across questions distinct questions; checks is the equivalence evaluations (sites

\times

merchants) that all agreed.

Operator	Buggy mutants	Diff. kills	Metamorphic kills	Structural kills	False admits
per_group_reducer	7	7	6	1	0
group_reduce_by_key	11	11	10	1	0
per_group_count	5	5	5	0	0
per_group_size	9	9	7	0	2
per_group_sum	13	13	11	2	0
group_reduce	13	13	11	1	1

Appendix

Table 5: Mutation study of the admission gate. For each admitted operator we generate every single-point mutant of its implementation, discard the ones that still match the original on every input (equivalent mutants), and run the rest through the gate. diff. kills is the uncorrelated model (only the implementation is mutated, the reference stays correct), where differential testing alone should catch the bug. metamorphic and structural kills are the correlated model (the same bug is written into both implementations, so differential cannot catch it), where only the conservation checks or a no-output rejection can catch it. false admits is

0/138

under the uncorrelated (independent-reference) model the loop uses, and

10/138

under the correlated worst-case, where the identical bug is written into both implementations so differential is blind and only metamorphic conservation remains. Validation on 63 synthetic merchants.

Operator	Construction	Uncorrelated	Correlated
per_group_sum	cyclic (relabel)	admitted	admitted
per_group_sum	swap (relabel)	admitted	admitted
per_group_sum	merge (control)	rejected	admitted
group_size	cyclic (relabel)	admitted	admitted
group_size	swap (relabel)	admitted	admitted
group_size	merge (control)	rejected	rejected

Appendix

Table 6: Adversarial, conservation-preserving wrong operators. Each construction is built to satisfy every relation per_group_sum or group_size declares (relabeling), or is a control that should not (merge). Validated against the same gate as the closed loop, under the two mutation-study threat models. The lone false admit, per_group_sum + merge under the correlated model, is bold.

Admission rule	Buggy	Adv.	False rej.
Oracle-free gate (uncorrelated)	0/138	4/6	1/14
Oracle-free gate (correlated)	10/138	5/6	1/14
LLM judge (same model, maj. of 5)	0/138	0/6	2/14

Appendix

Table 7: LLM-judge admission baseline versus the oracle-free gate, on the same pool (138 mutants, 6 adversarial constructions, 14 correct operators; 63 merchants). The judge is the same frozen model, majority vote over 5 reasoning samples per candidate; columns as in Table 1 .

category	questions	SQL (0-shot)	SQL (3-shot)	DSL acc.	mean SQL len.	mean DSL len.
flat	129	0.87	0.88	1.00	59	37
per-group	25	0.75	0.71	1.00	118	45
order-dependent	29	0.61	0.79	1.00	258	38
overall	183	0.81	0.84	1.00	n/a	n/a

Appendix

Table 8: Text-to-SQL baseline on the verified (question, expression) pairs (43 merchants), Qwen3.6-35B-A3B. Each question’s DSL expression is the exact gold; the model emits a SQLite query (best-of-5, majority vote over the executed results, temperature 0.4) run on a per-merchant transactions table and compared. To test the substrate rather than a deliberately minimal engine, SQL is granted the two analytics aggregates SQLite omits, median and population standard deviation (as Postgres/BigQuery/DuckDB provide), matching the DSL’s definitions. Accuracy is per query (each (question, merchant) instance scored against gold), the same convention as BookSQL (Table 12 ) and EHRSQL (Table 13 ). An authored reference SQL reproduces gold on all order-dependent instances (337/337), so every question is answerable in SQL. Numbers are the mean of 3 seeds (per-cell std

\leq 0.01

). Lengths are mean characters of the query; the DSL is exact by construction. The 3-shot column prepends three hand-authored (question, SQL) exemplars to the prompt (one GROUP BY, one ordered window, one granted aggregate), disjoint from the eval and illustrating form only; it lifts the order-dependent category (0.61

\to

0.79) at a small cost to per-group, confirming the order gap is largely elicitation rather than a substrate limit.

Outcome	Drafts	Share
Admitted	41	11%
Rejected by substrate (method-free)	270	70%
Method call or attribute access	196
Other banned syntax	74
Rejected by verification	64	17%
A metamorphic relation fails	44

Appendix

Table 9: Reach of the admission gate over 384 operator drafts from six induction runs. A draft must pass two filters in turn: the method-free substrate sandbox, then verification (differential and metamorphic). Most drafts are turned away by the substrate, not by verification, because the model reaches for a method call on a harder operator; verification, in turn, rejects almost only wrong operators. Sub-counts are indented.

Panel of Figure 6 — Figure 6: Base-model ablation on the merchant domain across all three starting sets (Amounts & Timing, Top Buyer, Timing), the seed-sensitivity companion to the cross-domain ladder of Figure 3 . Five base models per seed, same stacked convention: the light band at the base is the initial seed types (constant across base models), the solid above it is the additional subset expressible with the seed operators alone, hatched is the subset whose expression calls an induced operator, and the label above a bar is the number of operators admitted, shown when at least one answerable type uses them (omitted for zero admissions and for admitted-but-unused ones; e.g. 4B on Amounts & Timing admits four operators that no answerable type ends up using). 4B/8B/14B/32B are Qwen3 dense models, a controlled same-family, same-generation, same-architecture scale sweep; 35B is the Qwen3.6-35B-A3B mixture-of-experts main model ( $\approx$ 3B active parameters, a later generation), shown as a cross-architecture reference point. Discussed in Section 4.4 and Appendix P .

Base model	Starting set	Inner cov.	Gap	Drafts	Admitted	Final
Qwen3-4B (dense)	Amounts/timing	39	group_by, mode	320	4	39
	Top-buyer	17	mode	192	0	17
	Timing	36	latest	128	0	36
Qwen3-8B (dense)	Amounts/timing	57	mode	128	0	57
	Top-buyer	36	mode	64	0	36
	Timing	42	mode	192	0	42

Appendix

Table 10: Base-model ablation on synthetic data: the full closed loop re-run with four Qwen3 dense base models on the three starting sets and the fixed 63-merchant validation set, gate-topk

K=3

(Appendix B ), the same gate throughout. “inner cov.” is the answerable types the inner loop reaches on the seed operators; “gap” is the top-tallied missing capability the model discovers (each seed is given up to two induction rounds, hence some seeds show two gaps); “drafts” is the operator candidates proposed across all attempted gaps; “admitted” is how many pass the gate; “final” is the total answerable types after all rounds for that seed. The gate is sound at every scale: no false operator is admitted anywhere. Self-extension is not monotone in size: 8B authors no gate-passing operator on any of its

128

–

192

drafts per seed despite matching or exceeding 4B’s inner coverage, and 4B’s own four admitted operators unlock no further measured coverage in this run; the largest dense model, 32B, admits the most operators overall and is the only dense model to self-extend beyond amounts/timing, on both timing and top-buyer.

Proposer (family)	Amt	Buyer	Timing	BookSQL	EHRSQL	Admits	(median)
	Merchant seeds (final)			Transfer (final)		False	Compile
Qwen3.6-35B-A3B (main)	336	445	278	162	248	0	n/a
Mistral-Small-24B	302	258	243	158	147	0	31%
Gemma-3-27B	70	25	121	37	75	0	13%
Llama-3.3-70B	155	143	181	109	106	0	34%

Appendix

Table 11: Cross-family summary: the full closed loop re-run with three additional families (Mistral-Small-24B, Gemma-3-27B, Llama-3.3-70B) as the proposer, same frozen prompt and protocol as the main model, across the three merchant seeds and two transfer domains. Final is answerable types after both rounds; compile is the median fraction of proposed expressions that execute (the proposer’s DSL fluency). Every family admits zero wrong operators; discussion in § 4.4 .

	zero-shot				few-shot
model	agg	ratio	order	overall	order	overall
Qwen3-4B	1.000	0.667	0.500	0.800	0.750	0.800
Qwen3-8B	0.750	0.443	0.498	0.622	0.319	0.624
Qwen3-14B	0.993	0.667	0.250	0.729	0.507	0.868
Qwen3-32B	1.000	0.996	0.448	0.852	1.000	0.933
Qwen3.6-35B-A3B	1.000	0.859	0.514	0.842	0.990	0.944

Appendix

Table 12: Text-to-SQL baseline on a second domain, BookSQL (business-ledger accounts): 3,000 self-generated compositional questions (15 templates across three categories, 200 each) over 300 accounts. The same frozen base models emit a SQLite query (best-of-5, majority vote over the executed results, temperature 0.4, matching the merchant baseline of Table 8 and EHRSQL’s Table 13 ) over a flat per-account table that mirrors the DSL context one-to-one, so no query needs a JOIN. SQL is granted the median and population-standard-deviation aggregates SQLite omits, defined to match the DSL. Accuracy is per query (each (question, account) instance scored against gold), the same convention used throughout the merchant (Table 8 ) and EHRSQL (Table 13 ) baselines. agg is flat aggregation, ratio is a derived statistic (coefficient of variation, peak-to-average, daily volume), and order is a consecutive-entry gap statistic, needing an ordered window function in SQL. Numbers are the mean of 3 seeds (per-cell std

\leq 0.01

); the DSL is exact by construction. The few-shot columns prepend three hand-authored (question, SQL) exemplars (one GROUP BY, one ordered window, one granted aggregate), disjoint from the eval; few-shot sharply raises order for the larger Qwen models (32B/35B to

\approx

1.00) but is model-dependent, regressing Qwen3-8B and Gemma.

model	Compositional (main)	Compositional (few-shot)	Retrieval (supp.)
Qwen3-4B	0.635	0.852	0.809
Qwen3-8B	0.763	0.740	0.775
Qwen3-14B	0.774	0.850	0.848
Qwen3-32B	0.821	0.887	0.808
Qwen3.6-35B-A3B	0.911	0.917	0.958
Gemma-3-27B	0.885	† 0.768	0.859

Appendix

Table 13: Text-to-SQL baseline on a third domain, EHRSQL (MIMIC-III): the full verified pools (7,660 compositional and 4,500 retrieval instances) over 300 single-patient contexts. The same frozen base models emit a SQLite query (best-of-5, majority vote over the executed results, temperature 0.4, matching the merchant baseline of Table 8 ) over a flat per-patient table that mirrors the DSL context one-to-one, so no query needs a JOIN. SQL is granted the median and population-standard-deviation aggregates SQLite omits, defined to match the DSL. Accuracy is per query (each (question, patient) instance scored against gold). Compositional is the main track (self-generated statistical/ordered questions); Retrieval is a supplementary control of real EHRSQL attribute look-ups, where both systems are near ceiling. Numbers are the mean of 3 seeds (per-cell std

\leq 0.01

); the DSL is exact by construction. The Compositional (few-shot) column prepends three hand-authored (question, SQL) exemplars (one GROUP BY, one ordered window, one granted aggregate), disjoint from the eval; it lifts most Qwen backbones (4B

+0.22

, 14B

+0.08

, 32B

+0.07

) but is model-dependent: Gemma-3-27B drops ( † 0.768), where the window exemplar induces an aggregate-over-window ( AVG(LAG() OVER ...) ) that SQLite rejects, a form it avoided zero-shot with legal self-joins.

Panel of Figure 7 — Figure 7: Three independent starting sets converge on a shared answerable set. Bars count the quantities answerable in all three runs (the 3-way intersection of their answerable sets, compared by value signature on the shared 63-merchant validation set) at each induction stage. Before any induction the three share $38$ quantities, all expressible from their common seed operators and none per-group. After induction the shared core grows to $73$ , of which $19$ are per-group aggregations (hatched) that lie outside every starting set’s closure, so the convergence is in the induced capability, not the seed operators. The three do not collapse into one identical set (each also keeps exploring its own directions; final per-run sizes $326/435/268$ , pairwise overlaps $102$ – $118$ ); rather, from disjoint seeds they independently acquire the same per-group capability and a common set of exactly-computable quantities.

Quantity (same value on all 63 merchants)	Amounts/timing	Top-buyer	Timing
Median transactions per buyer	count_per_group	per_bsigner_count	mode_counts
Busiest hour’s transaction count	count_per_group	group_count	mode_counts
Buyers with more than one transaction	count_per_group	group_count	mode_counts
Busiest weekday’s transaction count	count_per_group	group_count	mode_count_by

Appendix

Table 14: Convergent evolution of operators. Each row is one quantity that ends up answerable in all three runs and evaluates to the same value on every one of the 63 merchants (identical value signature), yet each run computes it with a per-group operator its own outer loop authored and named independently. The starting set fixes the path, not the destination: three disjoint seeds reinvent the same capability under different names. Full expressions are in the committed convergence_results.json .

Large language model agent self-improvement studies how agents use experience and feedback to improve their behavior, tools, and workflows.

See all 277 papers

A Relative-Computability Theory of Self-Improving Agents
Apr 9, 2026Chien-Ping LuSelf-Improving Agents Recursive Self-Improvement
Skill $^{\infty}$ : Recursive Self-Improvement for Agent Skill Optimization
Oct 26, 2026Wangcheng Tao, Zhanglu Yan, Han Wu +1LLM Agent Self-Improvement LLM Agent Skill Learning
National University of Singapore · City University of Hong Kong
Reliable Self-Improvement Training by Verifying Reasoning, Not Just Answers
Mar 23, 2026Xinyu ZhangLanguage Model Self-Improvement Self-Training for Language Models
Anyscale

Apr 9, 2026J/K move · Enter open · S save

Chien-Ping Lu

Self-Improving Agents Recursive Self-Improvement

Open paper AskPDF arXiv

Agents increasingly modify the procedures by which they solve tasks and improve themselves. Autonomy over improvement, gains in practical capability, and enlargement of computational reach are distinct properties. We develop an oracle-relative model with mutable solvers, evaluators, and improvers. Uniform simulation keeps every total decision procedure produced by effective self-revision over

A

within

\mathcal{C}(A)=\{D:D\leq_T A\}

; oracle joins account for additional access, while the relativized limit lemma separates limiting answers from effective completion. A worked model of Boolean rule acquisition makes the distinction constructive. For a known finite-dimensional feature language, we characterize exactly which answers a query history determines, obtain a sharp teacher-query bound, and give a terminating protocol that permits revisions to the query proposer. The learned solver can dispense with the teacher on every input while remaining in the same computability layer. However, uniformly constructing the required feature-span specification from arbitrary effective feature programs is already as hard as the relative halting problem. We also give a conditional criterion for strict ascent and distinguish it from finite behavioral evidence. The framework thus separates acquisition, certification, and computability ascent, identifying both a positive route to verified support removal and the assumptions on which it depends.

Known before

Executable

Total answerable