CS Paper Radar

Proof-Carrying Evolution: Black-Box Search, White-Box Flight

Amit Jain, Sergio Sanchez-Hurtado, Victor Rodriguez-Fernandez, Richard Linares

cs.RO cs.NEeess.SY ·submitted 2026-10-30 17:06 UTC · v1

Abstract

We study whether a language model can help design controllers whose behavior can be formally checked. In proof-carrying evolution (PCE), a search proposes controllers together with their certificates. Their mathematical forms are fixed; a proposer chooses their numerical parameters together. Certificate checks guide selection, and only a certified candidate can be returned. The deployed artifact is a control law and its certificate; the language model is used only during design. We compare four language models with classical search and synthesis on docking under a speed limit, pursuit of a maneuvering target, and attitude control on SO(3), using paired runs and shared proposal allowances. Certificates are checked in exact rational arithmetic during search on the linear problems. On SO(3), the search uses floating-point checks, followed by exact re-verification of every reported champion. The best run of each method also receives Lean 4 proofs of its stated control properties. On the linear problems, the strongest models beat the standard classical baselines on every run, but a classical optimizer that chooses certificates for the same objective closes most of that lead. Among the cited pursuit champions, the ranking does not survive a change from Euler to zero-order-hold dynamics. On SO(3), no model detectably outperforms CMA-ES when mixed with classical mutation. When models write every proposal, one tested model improves on CMA-ES and the other performs worse than its mixed variant. All search medians remain below the hand-tuned law. In a docking control with the objective and mutation operator held fixed, retaining certified candidates yields new certified designs in every run; removing this rule yields none.

Closest papers

Nearest neighbours by meaning across the whole index.

Growing an Agent/Prover Interface: Evolutionary Tool Design for Cost-Efficient Theorem Proving in Rocq and Lean

cs.AI ·2026-09-30 ·Jules Viennot, Guillaume Baudart, Marc Lelarge
theoryhot direction similarity 0.61
Abstract

Recent achievements in AI-assisted mathematics require intensive interaction of agents with proof assistants to generate machine-checked proof certificates. Agents interact with proof assistants such as Rocq or Lean through an interface that controls what the agent receives from the prover and the cost of these interactions. Today, these interfaces are adapted from tools designed for humans and not optimized for agents. We propose an evolutionary method where a frontier model incrementally proposes new features and only keeps the ones that improve the overall performance of smaller models. We demonstrate the effectiveness of our method by growing, on a curated set of mathematical problems, ROCQ-MCP-EVOLVE, a new MCP server for the Rocq prover. On the held-out test split of miniF2F-Rocq, an agent equipped with ROCQ-MCP-EVOLVE outperforms both the baseline that only exposes the Rocq compiler and an established MCP server, across four models from two families, in success rate, cost per solve, and time per solve. Although evolved for Rocq, the resulting server transfers to Lean, improving cost and time per solve on a subset of PutnamBench. We release ROCQ-MCP-EVOLVE and its port to Lean.

0.30

CoToan: Executable Rules and a Representation Contract for Reproducible Game AI Evaluation

cs.AI ·2026-10-29 ·Ha-Thanh Nguyen
published similarity 0.59
Abstract · Accepted at RIVF 2027

Game AI results are comparable only when different implementations expose the same decision problem. Yet seemingly minor representation choices can silently change that problem by altering action probabilities or collapsing states with different outcomes. We study this issue through CoToan, an executable specification and representation contract for Vietnamese Mathematical Chess connecting the Game Description Language (GDL) with OpenSpiel. The game provides a useful case because a single capture may have multiple arithmetic justifications, while outcomes can depend on scoring rules and a finite playing horizon. CoToan therefore represents actions by their state transitions rather than by arithmetic witnesses, and treats time and victory configuration as part of task identity. Cross-representation tests show agreement in legal actions, successor states, and terminal outcomes across hundreds of sampled and constructed positions, complemented by exhaustive checks of all 32 operator masks and 512 opposing-material subsets. Controlled diagnostics further show that uniform witness-level sampling alters endpoint-action probabilities, while omitting remaining time or victory settings can merge states with different terminal behavior. These results show that action semantics, time, and victory configuration are not merely implementation details. They are part of the experimental task itself and must be represented explicitly for reproducible game AI.

0.37

Reap: Uncovering Monte Carlo proof search with a lightweight model

cs.AI ·2026-11-02 ·Yutong Wang, Xuanzhi Ren, Tianyi Xu, Ruitong Liu, Jingda Xu +3 more
similarity 0.58
Abstract

We present Reap, an open framework for learning and analyzing formal proof search in Lean4. Reap implements policy-value-guided Monte Carlo Tree Search directly in Lean, sharing proof-state transitions, AND-OR search, and replay verification between inference and training rollouts. Structured action logs expose how neural predictions and tactic execution interact during search. Using this framework, we train Reaper-1, a 1.7B-parameter policy-value model, through continued pre-training, supervised tactic learning, and iterative search-based reinforcement learning. Using a separate premise selector, the final system solves 79.9% of miniF2F-test at pass@32, establishing state-of-the-art performance among open provers of comparable size while remaining competitive with substantially larger models. Beyond improved solve rates, our results suggest that RL strengthens the prover's ability to organize proofs around useful intermediate results, favoring substantial advances over repeated local adjustments. This more directed proof construction is accompanied by increasingly elaborate tactic programs: fewer explicit search decisions are needed, while more work is performed within each decision. The resulting trade-off between search effort and tactic execution cost provides insight into how learning changes the prover's problem-solving strategy.

0.09

Reachable Global Optimization in AI Systems: How Global Is Global?

cs.AI ·2026-08-20 ·Wesley Shu
benchmarktheory similarity 0.58
Abstract

AI systems increasingly claim to optimize prompts, policies, architectures, plans, tool-use trajectories, reasoning traces, and test-time computation. This paper argues that such claims are underspecified unless they state the region actually reachable by the system that performed the optimization. We introduce Reachability-Induced Optimization (RIO), a model in which a generator, verifier, controller, memory, tools, and budget induce a reachable candidate region. The returned solution is therefore a best visited point, an approximate reachable optimum, or an exact global optimum only when additional certificates relate the reachable region to the full formal space. We prove reachable-optimality, false-globality, gap- decomposition, certificate, escape, pruning, and control-value results. The full benchmark record contains 66,150 executed trials over six known-optimum landscape families, seven control policies, 270 landscapes, and 35 runs per landscape-method. The online appendix includes raw trial records, aggregate tables, figures, benchmark code, validation scripts, and checksums. The results show that control can restrict, expand, or misdirect reachability, and that optimization quality, reachability quality, and control reliability must be reported separately.

0.24

One Perturbation Is Not Enough: Identifiability and Blind Baselines for Behavioral AI Evaluation

cs.CV ·2026-09-05 ·Rasul Khanbayov, Mariam Sohail, Ahmed Abdala, Hasan Kurban
survey similarity 0.57
Abstract

Behavioral evaluations perturb an input and read the induced change in the output in order to certify that a system uses that input. We show that the number of perturbations such a certificate requires is fixed, and that reporting a single perturbation cannot supply it. Where a response ratio is a property of the policy rather than of the test items, the behavioral record is a linear measurement of an exponent vector recording how much the output depends on each input, so perturbations identify input use exactly when their logarithms span the input space. At least $n$ are needed for $n$ inputs, an incomplete design confuses precisely the policies differing along the kernel of its design matrix, and sharpening a perturbation never substitutes for adding an independent one. We also derive in closed form the score such a test awards a policy that reads nothing, which is far from zero and which none of the probes we survey reports. Instantiating this where the correct response is fixed by dimensional analysis, we run a complete identifying set of three perturbations on three vision--language models reporting a physical quantity from video. All three score far below their own blind bound rather than above it, because each defaults to one of a small set of round calibration values that never matches what the scale asserts; none moves its relabeling response by a single exponent, and none is separable from the same model instructed to ignore the video.

0.22

Executor-aware Candidate Selection via a Feasibility Certificate

cs.RO ·2026-09-29 ·Sooin Choi, Soonwoong Hwang, Wansoo Kim
similarity 0.57
Abstract · 8 pages, 6 figures

Modular robotic systems often separate motion planning from a downstream executor that enforces state-dependent hard constraints. A candidate that is geometrically valid may therefore be incompatible with the executor's available command set. We present a certificate-based candidate-selection framework that constructs a command witness from the executor hard set at predicted rollout states and verifies it against the original constraints, without changing candidate generation, ranking, or the executor. Across 5,085 geometry-valid numerical evaluations on two robot models, 795 admitted no executor-feasible command. The certificate is sufficient but conservative: none of the 795 was certified, while 7.09\% of reference-feasible cases remained uncertified. In controlled FR3 and fixed-base RB-Y1 simulations, certificate admission frequently changed candidate selection, and a post-hoc exact linear-programming (LP) admission baseline revealed platform-dependent conservatism. Relative to geometry-based selection, certificate admission was associated with lower planner-command coverage and higher nominal tracking error, without a consistent advantage in reached-state interaction reserve. A planner-generated MoveIt/OMPL study further evaluates the same admission rule on externally generated candidate pools.

0.19

TLAPS-Bench: Formally Proving Correctness of Real-World System Specifications with TLA+ Proof System

cs.AI cs.DCcs.LOcs.SE ·2026-11-02 ·Qian Cheng, Ruize Tang, Saad Mohammad Rafid Pial, Zhizhen Cathy Cai, Yiming Su +11 more
benchmarkcode/data similarity 0.56
Abstract · 35 pages (10-page main text, references, and appendix), 7 figures, 20 tables. Benchmark and harness: https://github.com/specula-org/TLAPS-Be…

TLAPS-Bench is a benchmark and execution harness for constructing machine-checked proofs for real-world system specifications in TLA+ with agentic AI. Proving correctness of complex system specifications requires discovering inductive invariants, reasoning about intricate state transitions, and decomposing proofs into tractable obligations. TLAPS-Bench provides a proof harness that supports iterative proof development atop the TLA+ Proof System (TLAPS), where agents are equipped with proof tools and libraries, with safeguards against reward hacking. Using the harness, we have employed AI agents to prove desired properties for important system specifications that were not proved before, spanning cache coherence, Byzantine consensus, and write-ahead logs. TLAPS-Bench contains 265 proof targets (each encodes a property to prove) from 95 TLA+ specifications of real-world systems. We evaluated frontier AI agents, represented by Codex with GPT models, on a subset of 70 proof targets across 12 specifications. The highest-scoring model, GPT-6.1 Sol (max), proved 31 (44.3%) proof targets. The results show challenges and opportunities in end-to-end proof development.

0.23

JEV-Star: Fast, Low-Cost StarCraft II Control with Language-Model Planning

cs.GT ·2026-09-23 ·Weiyu Ma, Liangbing Zhao, Yongcheng Zeng, Jian Zhao
code/datahighly cited similarity 0.56
Abstract

We present JEV-Star, a StarCraft II controller that defeats the strongest non-cheating built-in AI, Lv7, by combining fast JEV action selection with persistent GPT-6 planning. The combined system wins four full games at Lv5--Lv7, including two Lv7 victories with different seeds, while retaining a median JEV response time of 0.422 seconds. Mean estimated model cost across these games is USD~3.71 per game: USD~0.15 for JEV and USD~3.56 for GPT-6. We compare this system with an initial JEV-only controller in full-game macro control and multi-unit micromanagement. The standalone controller reaches a 20-minute limit against Lv2 without expanding. Across 35 battle maps with three episodes per map and controller, the combined system raises mean enemy elimination from 16.50\% to 37.69\% and wins from 3 to 7 out of 105. Replay frames and decision logs document resource reservation, persistent economic goals, and stable army objectives in successful full games. The results demonstrate a practical division between inexpensive, subsecond decisions and longer-horizon planning. The comparison evaluates complete systems; concurrent interface improvements mean that planning's contribution is not isolated by a controlled ablation. Code is available at https://github.com/sc2musa/Jev_Star

0.72