acceptodds
Withdrawn from ICLR 2027

Second-Order Problem Solving for Recursive Self-Improvement in Formal Verification

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Recursive self-improvement (RSI) enables agents to iteratively optimize their workflows via execution feedback. However, standard RSI typically operates as a first-order optimizer: it repeatedly patches surface-level parameters in response to immediate failure symptoms, often leading to trial-and-error thrashing without resolving underlying mechanisms. To address this limitation, we introduce SO-RSI, a framework that elevates workflow optimization to a second-order diagnostic inquiry—investigating why failures occur before committing to structural interventions. SO-RSI passively monitors execution traces for three structural anomalies (recurrence, opposing edits, and expectation mismatch) to trigger targeted mechanism investigations. By executing lightweight diagnostic probes and maintaining persistent inquiry memory across RSI rounds, SO-RSI accumulates causal evidence to guide systematic workflow edits rather than parameter patches. Across Lean 4 proof generation and Verus-based verifiable code generation, SO-RSI improves final held-out pass rates over Naive RSI by 21.8 and 25.8 percentage points under matched 24-hour search budgets. Behavioral analyses further confirm that SO-RSI substantially suppresses failure recurrence and eliminates unproductive zero-progress optimization loops.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Recursive Self-Improvement, Second-Order Problem Solving, LLM Agents, Formal Verification, Automated Theorem Proving

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.80 over 5 reviews, above 27% of the others.
Reviewer_oj7VOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes a framework for improving recursive self improvement agents by diagnosing underlying workflow failures rather than repeatedly applying superficial fixes. The approach detects three types of anomalies: recurring failures, opposing edits, and expectation mismatches. It riggers investigations that formulate hypotheses, execute diagnostic probes, and preserve evidence across optimization rounds. The resulting evidence guides subsequent workflow modifications. Experiments on Lean theorem proving and Verus verifiable code generation report improvements over naive RSI.

Critical strengths
  • the work builds a practical and interpretable framework by combining anomaly detection, hypothesis testing, executable probes, and persistent investigation memory to provide a coherent approach to workflow improvement. The distinction between testing a hypothesis and merely evaluating a proposed edit is useful.

  • it shows promising empirical improvements where the it reported gains across two formal verification settings. Ablation studies and behavioral analyses provide additional evidence that diagnostic probing and persistent memory can improve workflow optimization.

Critical weaknesses
  • the experiments compare primarily against Naive RSI. Stronger comparisons, such as an always-on diagnostic agent, a reflection-based RSI agent, or a HarnessFix-style diagnostic approach, would help determine whether the improvements come from the proposed second-order framework or simply additional structured reasoning.

  • evaluation has very limited scale as it uses only 48 Lean and 46 Verus held-out tasks, three independent runs, and one outer improvement model. Moreover, aggregate token costs are not reported, limiting the analysis of computational efficiency.

  • the core ideas of diagnosing failures, executing tests, and maintaining experience are individually established in prior work, particularly HarnessFix and AutoManual. The main novelty appears to be their integration with selective anomaly detection, but the paper does not sufficiently isolate the contribution of this selection mechanism.

Questions for authors
  1. How does SO-RSI compare with stronger diagnostic baselines? Would always performing root-cause investigation, without anomaly-triggered selection, achieve comparable results under the same budget?

  2. Since mechanism classification and interpretation involve LLM reasoning and human auditing, could the authors report inter-annotator agreement and provide concrete examples where diagnostic probes successfully distinguish competing explanations?

  3. How sensitive is performance to the anomaly detection strategy? An ablation separating recurrence, opposing edits, and expectation mismatch would clarify which signals contribute most to the improvements.

Reviewer_9oXVOpenReview ↗
Rating
2
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper distinguishes direct patching from mechanism-based diagnosis in recursive self-improvement of agent workflows. After coding 134 attempts across five Lean 4 trajectories, it proposes SO-RSI: detect recurrence, reversals, and expectation mismatches; form falsifiable hypotheses; execute diagnostic probes; and transfer evidence to an editing agent through persistent investigation memory. Across three 24-hour runs, held-out pass rates reach 71.2% for Lean and 59.2% for Verus-based code generation, compared with 49.4% and 33.4% for Naive RSI. Removing probes or memory provides ablations intended to explain the gains.

Critical strengths
  1. The problem and coding criteria are clearly defined. F/H/I/G/U distinguish direct repair, untested hypotheses, investigation, evidence-guided intervention, and insufficient records. The scheme does not automatically treat eventual performance gains as confirmation of a mechanism or infer investigations from missing records.
  2. The main results and ablations are informative. Both formal-verification domains show substantial held-out gains, and removing probes or memory targets key design choices. Unknown labels and count denominators are retained, and the authors acknowledge that behavioral statistics alone do not identify causal effects.
Critical weaknesses
  1. Units and observability in the behavioral analysis are not yet comparable. The motivation study reports 134 attempts, while the main experiments contain thousands of episodes. Without a mapping or run lengths, their proportions cannot be directly compared; different counts alone do not establish a contradiction. SO-RSI produces structured investigation records, while Naive RSI mainly produces free text, so record density may influence episode reconstruction even when method names are hidden. Mechanism-recurrence checks also depend on each method's mechanism descriptions, requiring common definitions, audit coverage, and agreement statistics. Without this evidence, the behavioral tables cannot independently support the explanation that more second-order investigation causes the gains.
  2. The independent source of gains and resource fairness remain unclear. Matching 24 hours matches wall-clock time, but not necessarily total compute without tokens, concurrency, hardware, and evaluation/probe accounting. Actual runtimes are unknown, so per-task timeout limits alone cannot establish undisclosed parallelism. Simpler controls such as prompted diagnosis or continuous investigation and direct comparisons with cited related systems are missing. Removing probes preserves much of the Lean gain but approaches baseline on Verus, suggesting domain-dependent mechanisms. Missing proposed/accepted/withdrawn edit counts, prompts, and code also prevent excluding suppression of bad edits as an explanation. The abstract's claim to eliminate zero-progress loops should be reconciled with nonzero values of 7.2 and 8.6. These concerns lead me to lean toward rejection, with reassessment possible after clarification.
Questions for authors
  1. Units: What are the exact definitions and mapping of attempts and episodes? Please report run lengths, attempt counts, and G-edit counts for the five motivation trajectories and three main runs.
  2. Existing budget records: Please report tokens, hardware/concurrency, evaluation counts, probe time, and proposed, accepted, and withdrawn edits by method and run.
  3. Behavioral audit: How many annotators participated, what were their roles, and what was agreement before adjudication? How was greater episode observability from structured records controlled, and how were Naive RSI's mechanism checks and eligible cases frozen?
  4. Mechanism differences: How do the authors explain the no-probe result of 63.4 on Lean versus 33.0 on Verus? Are prompted-diagnosis, matched-record-format, or continuous-investigation controls already available?
  5. Statistics and reproducibility: What are the denominators for zero-progress loops, and how was "no cost benefit" judged? Please state the availability of code, complete prompts, and evidence files, and replace "eliminates" with the supported claim of "reduces."
Reviewer_nytPOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper proposes SO-RSI, where an LLM agent edits an agent workflow based on execution feedback. The authors argue that standard RSI (although there is no standard RSI, and the authors' RSI definition is definitely not correct) mostly patches failure symptoms, based on an annotation of 134 attempts from five Lean RSI trajectories. SO-RSI adds an LLM detector for recurring failures, opposing edits and unmet expectations, an investigation step that runs diagnostic probes, and a persistent memory of these investigations. With GPT-5.6 Sol as the outer agent and GPT-5.4 as the inner model, the paper reports gains of 21.8 and 25.8 points over Naive method on Lean proving (48 test problems) and Verus code generation (46 test problems).

Critical strengths
  1. The paper tackles an important and timely problem of making self-improving agents more reliable.
Critical weaknesses

To the best of my knowledge, the use and definition of the term "RSI" is incorrectly used in the paper. I will still refer to it as RSI for consistency with the author's terminology.

Reported Pass Rates Are Impossible With the Stated Test Sets: With 48 Lean and 46 Verus test problems, a single run gives pass rates in steps of 2.08 and 2.17 points, and a mean over three runs in steps of 0.69 and 0.72 points. None of the 10 pass rates in Tables 3 and 4 fits either case. Eg S0 is 29.4 on Lean (14/48 = 29.2, 15/48 = 31.3) and 14.8 on Verus (6/46 = 13.0, 7/46 = 15.2). 14.8 is also exactly the score of the RSI-Exam Lean seed on its 54-problem dev split (8/54).

All Curves in Figure 3 Have the Same Shape: All four curves (two methods, two domains) go up and down at exactly the same checkpoints over all 12 steps, and each SO-RSI step is about twice the matching Naive RSI step. Independent runs of different methods on different domains should not regress at the same checkpoints. Together with the point above, I can't trust the reported results without the code, the RSI traces and the per-run, per-task results, none of which are provided.

Behavioral Numbers Don't Add Up: a.) Tables 5 and 12 imply about 248 points of dev gain per SO-RSI run on Lean from G edits alone (76 edits with a mean gain of 9.8, over three runs), while a pass rate can go up by at most 100. Table 2 has the same problem, with about 158 points of edit gains per trajectory against a mean final gain of 18.8. b.) Section 3 finds about 9 mechanism hypotheses per Naive RSI trajectory, while Table 12 reports about 613 investigation episodes per Naive RSI run. c.) About 17,500 episodes were labeled by "independent reviewers", with no details on who they are or their agreement. d.) On Verus, w/o memory is close to SO-RSI on the behavioral metrics, but its pass rate (36.7) is close to Naive RSI (33.4), so these metrics don't explain the gains either.

Naive RSI Is the Only Baseline, and Budgets Aren't Matched: There is no comparison with any existing method, eg Meta-Harness, Self-Harness, HarnessFix, SICA, ADAS or GEPA, even though line 431 says prior work already establishes "self-modification and mechanism diagnosis". It is also unclear whether Naive RSI gets the same tools and history access as SO-RSI. The "matched 24-hour budget" is only wall-clock time. Line 132 says token use and verifier calls are reported, but line 809 says token cost is not reported, while SO-RSI runs 75% to 99% more investigation episodes than Naive RSI (Table 12).

Overclaiming: The abstract says SO-RSI "eliminates" zero-progress loops, but Table 5 still shows 7.2 and 8.6 per 100 edits. The lemma-retrieval example that motivates the paper (Figure 1) is only illustrative (Table 8), and the paper shows no real SO-RSI investigation or final workflow.

Questions for authors

Please see Weaknesses above.

In addition, can the authors confirm whether this paper is "completely AI-generated"?

Reviewer_UvASOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

SO-RSI improves fixed-model Lean and Verus workflows through anomaly-triggered investigation, executable diagnostic probes, and investigation memory retained across optimization rounds. Under matched 24-hour search budgets, the authors report gains of 21.8 and 25.8 percentage points over Naive RSI. Ablations examine the contributions of probes and memory.

Critical strengths
  • The probes make failure explanations testable.

  • Both domains show promising gains, supported by probe and memory ablations.

Critical weaknesses
  • The added value over HarnessFix is not established clearly enough. The choice and coverage of the three anomaly triggers also need more justification.

  • The experiments do not isolate the trigger policy from the investigation itself. Evidence that repairs remain effective across later rounds is also limited.

Questions for authors

Method clarification:

  1. What specifically is new compared with HarnessFix? Why not compare with it in experiments?
  2. Beyond the three predefined anomaly types, which investigation decisions follow fixed rules and which are generated by the model? How did you check whether these choices are appropriate and what failures they miss?

Experimental validation:

  1. As additional controls, could you compare against always-on and rate-matched random investigation under the same budget?
  2. For the existing experiments, is each candidate evaluated on the full development set? How are recurrence cases selected, and are repairs tracked across later rounds?
Reviewer_C1NcOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper introduces SO-RSI, a framework for improving LLM-based formal-verification workflows by investigating why failures occur. It detects repeated failures, opposing edits, and outcomes that contradict expectations. These signals trigger targeted diagnostic checks, whose findings are stored across improvement rounds and used to guide changes to the workflow. The main contributions are an analysis of 134 optimization attempts across five Lean trajectories, the SO-RSI framework, and experiments examining the value of executable diagnostic checks and persistent investigation memory. The approach modifies the agent’s workflow, including retrieval, generation, and repair procedures.

Critical strengths
  • SO-RSI connects recurring failures to testable hypotheses, executable checks, and workflow changes, while retaining findings across rounds. This provides a concrete approach to reducing repeated, unproductive edits in self-improving agents.
  • Under matched 24-hour budgets, SO-RSI reports gains of 21.8 and 25.8 percentage points over Naive RSI on Lean and Verus. Removing diagnostic checks or persistent memory lowers performance, supporting the value of both components.
  • Across 134 optimization attempts in five Lean trajectories, only 15 include diagnostic checks. This identifies a concrete gap between suggesting explanations and testing them, giving the proposed framework an empirical basis.
  • The paper tracks hypothesis testing, evidence-driven decision changes, recurring failures, and unproductive editing loops. These measures help assess whether higher pass rates are accompanied by a more productive improvement process.
Critical weaknesses
  • Reported means such as 71.2% on 48 Lean problems across three runs do not match the stated averaging of binary task outcomes. Additional averaging may explain this, but it is not documented. Raw solve counts and precise aggregation are needed to trust the headline gains.
  • The evaluation uses Naive RSI and component ablations, but lacks a stronger baseline that already performs explicit diagnosis and retains findings. It also does not isolate the benefit of anomaly-triggered investigation. This limits confidence in the framework’s specific contribution.
  • The paper does not report annotator agreement, audit coverage, or run-level uncertainty for recurrence and editing-loop metrics. These gaps weaken confidence that the reported behavioral improvements are reliable and representative.
  • Runs share a 24-hour limit, but total token use, verifier calls, and investigation overhead are not reported. This leaves the practical expense of the gains unclear and limits conclusions about efficiency.
Questions for authors
  • Can you provide solved/total counts for each run and explain the exact averaging procedure? For example, how is 71.2% obtained from 48 Lean test problems across three runs?
  • How many interventions and cases were audited, how were they selected, and what was annotator agreement before resolving disagreements? Are recurrence and editing-loop results consistent across runs?
  • Do you have comparisons with a diagnosis-oriented optimizer or a variant that investigates every round? These would help establish whether anomaly-triggered investigation adds value beyond diagnostic tools and persistent memory.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.