AI-Assisted Discovery of Convex Relaxations via Dual Agents

Mert Pilanci; Sungyoon Kim

arxiv: 2606.31182 · v1 · pith:MMCRD5VAnew · submitted 2026-06-30 · 💻 cs.AI

AI-Assisted Discovery of Convex Relaxations via Dual Agents

Sungyoon Kim , Mert Pilanci This is my paper

Pith reviewed 2026-07-01 06:02 UTC · model grok-4.3

classification 💻 cs.AI

keywords convex relaxationsdual agentslower boundsautocorrelation inequalityErdős minimum-overlap constantinterval arithmeticdual-feasible pointsAI-assisted discovery

0 comments

The pith

Dual AI agents discover tightening constraints that raise certified lower bounds on two optimization constants.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that LLM agents can systematically improve convex relaxations of nonconvex problems by having one agent propose new constraints and another verify their validity while hunting for counterexamples. Every reported improvement is backed by an explicit dual-feasible point that is checked with rigorous interval arithmetic, ensuring the bound holds for every admissible function. This method is applied to two constants previously studied via upper-bound searches: the first autocorrelation inequality and the Erdős minimum-overlap constant. The approach yields concrete numerical gains over prior certified values. A sympathetic reader would care because tighter relaxations deliver stronger, machine-verifiable guarantees without relying on manual constraint design.

Core claim

We instantiate the autoresearch paradigm to discover such relaxations: a coding agent proposes valid tightening constraints, a theory agent verifies each one and searches for counterexamples, and every reported bound is certified by an explicit dual-feasible point checked in rigorous interval arithmetic. On two optimization constants studied by tao2025alphaevolve - the first autocorrelation inequality (C_{6.2}) and the Erdős minimum-overlap constant (C_{6.5}) - we improve the certified lower bounds from 1.28 to 1.2937 and from 0.379005 to 0.37912, respectively.

What carries the argument

Dual agents (coding agent proposing constraints, theory agent verifying them) paired with dual-feasible points certified by interval arithmetic.

If this is right

The first autocorrelation inequality now carries a certified lower bound of 1.2937.
The Erdős minimum-overlap constant now carries a certified lower bound of 0.37912.
The same dual-agent procedure can be rerun on other constants whose lower bounds derive from convex relaxations.
All new bounds rest on explicit, machine-checkable dual points rather than heuristic arguments.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Pairing this lower-bound method with the upper-bound constructions from the cited prior work could narrow the gap between known bounds on these constants.
The verification loop might be extended to problems outside sharp-constant inequalities, such as certifying robustness margins in control or machine learning.
If the theory agent can be strengthened to propose its own relaxations, the process could become fully autonomous.

Load-bearing premise

The constraints proposed by the coding agent constitute valid tightening constraints for the convex relaxation, as verified by the theory agent, and the resulting dual-feasible points correctly certify the improved lower bounds via interval arithmetic.

What would settle it

Discovery of a feasible function violating one of the new certified bounds or a counterexample showing one proposed constraint is not valid would falsify the claimed improvements.

Figures

Figures reproduced from arXiv: 2606.31182 by Mert Pilanci, Sungyoon Kim.

**Figure 1.** Figure 1: The framework. The automated block (purple, dashed) alternates between a coding agent that adds or tightens a constraint and a theory agent that verifies its validity and searches for counterexamples; accepted constraints update the relaxation, and the loop repeats. On termination it yields the final relaxation, which a human verifies and compactifies; the resulting bound is certified by an explicit dual-f… view at source ↗

**Figure 2.** Figure 2: Certified primal objective of the convex program as a function of the loop iteration (version). The objective increases as the coding agent adds or tightens valid constraints; points in red are proposals the theory agent rejected as invalid (failing for some admissible f), as opposed to merely non-binding [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗

**Figure 3.** Figure 3: A representative exchange from the loop (condensed). The coding agent restricts to even f to make progress; the theory agent verifies the proof but flags that the even restriction is a genuine loss of generality, so the bound does not apply to C6.2, and redirects the search. Iteration v14 follows this recommendation and obtains the first rigorous bound on the unrestricted constant. Two limitations also ind… view at source ↗

**Figure 4.** Figure 4: Splitting (h, p) for lower bound verification. 25 [PITH_FULL_IMAGE:figures/full_fig_p025_4.png] view at source ↗

**Figure 5.** Figure 5: v7 rigorous proof.md, evidence of even function limitation verdict.md v7 [snippet selected] (theory agent) [PITH_FULL_IMAGE:figures/full_fig_p026_5.png] view at source ↗

**Figure 6.** Figure 6: v7 verdict.md sampled, theory agent correction rigorousproof.md v14 [snippet selected] (coding agent) [PITH_FULL_IMAGE:figures/full_fig_p026_6.png] view at source ↗

**Figure 7.** Figure 7: v14 rigorous proof.md, evidence of correction 26 [PITH_FULL_IMAGE:figures/full_fig_p026_7.png] view at source ↗

read the original abstract

Recent work shows that LLM agents can improve sharp-constant inequalities by searching for extremal constructions, which yield upper bounds. We address the complementary side: a lower bound holds for every admissible function and follows from a convex relaxation of the nonconvex problem, with tighter relaxations giving stronger bounds. We instantiate the autoresearch paradigm to discover such relaxations: a coding agent proposes valid tightening constraints, a theory agent verifies each one and searches for counterexamples, and every reported bound is certified by an explicit dual-feasible point checked in rigorous interval arithmetic. On two optimization constants studied by \citet{tao2025alphaevolve} - the first autocorrelation inequality ($C_{6.2}$) and the Erd\H{o}s minimum-overlap constant ($C_{6.5}$) - we improve the certified lower bounds from $1.28$ to $1.2937$ and from $0.379005$ to $0.37912$, respectively.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Dual-agent LLM setup produces small but certified improvements on two specific lower bounds, with the numerical claims standing independently via explicit dual points.

read the letter

The main point is that the paper pairs a coding agent that proposes tightening constraints with a theory agent that verifies them and hunts for counterexamples, then certifies the resulting lower bounds on two constants via explicit dual-feasible points checked in interval arithmetic. This yields improvements from 1.28 to 1.2937 on the first autocorrelation inequality and from 0.379005 to 0.37912 on the Erdős minimum-overlap constant.

The dual-agent design is the clearest new piece. Prior LLM work on these problems leaned toward upper-bound constructions, so shifting to lower bounds through better convex relaxations fills a gap. The verification step and the insistence on interval-arithmetic certificates are practical strengths; the final numbers do not depend on trusting the agents once the dual points are reported.

The improvements themselves are modest and narrow. They apply only to these two instances from the Tao et al. work, and the numerical lifts are incremental rather than transformative. The discovery process still involves LLM trial-and-error, even if the theory agent reduces some of the risk. No evidence of post-hoc selection or derivation gaps shows up in the certification step itself.

The paper is aimed at researchers who work on extremal inequalities or on LLM tools for sharpening mathematical bounds. A reader already following the Tao constants or similar optimization problems would find the concrete certificates and the agent workflow useful as an example. It shows honest engagement with the existing literature and supplies independently checkable outputs, so it deserves a serious referee.

Referee Report

0 major / 3 minor

Summary. The manuscript presents an autoresearch framework in which a coding agent proposes candidate tightening constraints for convex relaxations of non-convex optimization problems and a theory agent verifies validity or finds counterexamples; the resulting relaxations are used to produce certified lower bounds on two constants previously studied by Tao et al. (the first autocorrelation inequality C_{6.2} and the Erdős minimum-overlap constant C_{6.5}). The reported improvements are from 1.28 to 1.2937 and from 0.379005 to 0.37912, respectively, each supported by an explicit dual-feasible point whose objective value is validated by rigorous interval arithmetic.

Significance. If the numerical certificates hold, the work is significant because it supplies a concrete, reproducible instance of LLM agents contributing to the discovery of sharper convex relaxations while maintaining an independent, machine-checkable certificate that does not rely on the agent process itself. The explicit dual-feasible points and interval-arithmetic verification constitute a clear methodological strength that allows any reader to confirm the claimed bounds without re-running the agents.

minor comments (3)

[§3] The description of how the theory agent enumerates and checks candidate constraints (including any termination criteria or search heuristics) should be expanded in §3 so that the discovery procedure can be replicated independently of the specific LLM calls.
[Table 1] Table 1 (or the equivalent summary table of discovered constraints) lists several inequalities without indicating which ones were ultimately used in the final dual-feasible points for C_{6.2} and C_{6.5}; adding a column or footnote that links each constraint to the reported bound would improve traceability.
[Appendix] The interval-arithmetic certification is presented only for the final numerical values; a brief appendix entry showing the exact dual vector (or its rational approximation) together with the interval bounds on the objective would make the certificate fully self-contained.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading and positive evaluation of the work. The recommendation for minor revision is noted; however, the report contains no specific major comments requiring response. We will incorporate any minor editorial suggestions during revision.

Circularity Check

0 steps flagged

No significant circularity; bounds independently certified

full rationale

The paper improves two lower bounds via agent-proposed convex relaxations, but every reported bound is supported by an explicit dual-feasible point whose value is verified by rigorous interval arithmetic. This certificate is independent of the discovery process and can be re-checked from the reported point alone. No self-definitional steps, fitted inputs renamed as predictions, or load-bearing self-citations appear in the derivation chain. The citation to tao2025alphaevolve supplies only the baseline values being improved and does not underpin the new certificates. The central claim therefore stands on external mathematical verification rather than reducing to its own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Based on abstract only; the approach rests on standard domain assumptions in convex optimization and rigorous numerics. No free parameters, invented entities, or ad-hoc axioms are mentioned.

axioms (2)

domain assumption Convex relaxations of non-convex problems yield valid lower bounds.
Foundational premise for using relaxations to certify lower bounds on optimization constants.
standard math Interval arithmetic provides rigorous verification of dual feasibility.
Standard technique invoked for certification of the reported bounds.

pith-pipeline@v0.9.1-grok · 5689 in / 1273 out tokens · 36857 ms · 2026-07-01T06:02:31.980155+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

11 extracted references · 2 canonical work pages

[1]

See if you have folder v0

This is the initial step. See if you have folder v0. If you do, then run the code as a baseline to check that it works. If there is no v0, you can come up with the most naive version of the convex optimization problem that can be meaningful. After this you have an iterative loop
[5]

Name it as rigorousproof.md 18 AI-Assisted Discovery of Convex Relaxations via Dual Agents

Store the proof in the current version folder. Name it as rigorousproof.md 18 AI-Assisted Discovery of Convex Relaxations via Dual Agents
[8]

Erd\h{o}s’ minimum overlap problem,

IF the verdict was INVALID, go to 2 and propose a different constraint that makes mathematical sense. *** THINGS TO CONSIDER *** - A validation should take less than 10 minutes. Don’t heavily optimize the parameter space (split the original problem into too many different convex optimization problems) or increase the problem parameters too much. Our job i...

work page arXiv
[9]

See if you have folder v0

This is the initial step. See if you have folder v0. If you do, then run the code as a baseline to check that it works. If there is no v0, you can come up with the most naive version of the convex optimization problem that can be meaningful. 20 AI-Assisted Discovery of Convex Relaxations via Dual Agents After this you have an iterative loop
[10]

Then, create {nextversion} folder and copy the contents from the previous folder

Read the most recent version folder. Then, create {nextversion} folder and copy the contents from the previous folder
[11]

The proposal should not be something like a hyperparameter tweak; we will enhance the hyperparameters after the convex program has converged

Come up with a novel proposal that improves upon the previous implementation. The proposal should not be something like a hyperparameter tweak; we will enhance the hyperparameters after the convex program has converged
[12]

rigorous

After you come up with a proposal, you have to generate a "rigorous" proof that the constraint indeed holds. For an example see Lemma 3,4,5 in the convex optimization problem of White and how it is related to the convex optimization problem in section 5
[13]

Name it as rigorousproof.md

Store the proof in the current version folder. Name it as rigorousproof.md
[14]

It will be in the same folder, verdict.md

Now this is the important: you should be idle until the theorist agent reads your proof and gives a verdict. It will be in the same folder, verdict.md. If the verdict is VALID, it means your proposed proof is rigorous and makes sense. If the verdict is INVALID, it means your proposed proof has a flaw
[15]

IF the verdict was VALID, implement the constraint in the convex problem
[16]

should I keep going?

IF the verdict was INVALID, go to 2 and propose a different constraint that makes mathematical sense. *** THINGS TO CONSIDER *** - A validation should take less than 10 minutes. Don’t heavily optimize the parameter space (split the original problem into too many different convex optimization problems) or increase the problem parameters too much. Our job i...

work page arXiv

[1] [1]

See if you have folder v0

This is the initial step. See if you have folder v0. If you do, then run the code as a baseline to check that it works. If there is no v0, you can come up with the most naive version of the convex optimization problem that can be meaningful. After this you have an iterative loop

[2] [5]

Name it as rigorousproof.md 18 AI-Assisted Discovery of Convex Relaxations via Dual Agents

Store the proof in the current version folder. Name it as rigorousproof.md 18 AI-Assisted Discovery of Convex Relaxations via Dual Agents

[3] [8]

Erd\h{o}s’ minimum overlap problem,

IF the verdict was INVALID, go to 2 and propose a different constraint that makes mathematical sense. *** THINGS TO CONSIDER *** - A validation should take less than 10 minutes. Don’t heavily optimize the parameter space (split the original problem into too many different convex optimization problems) or increase the problem parameters too much. Our job i...

work page arXiv

[4] [9]

See if you have folder v0

This is the initial step. See if you have folder v0. If you do, then run the code as a baseline to check that it works. If there is no v0, you can come up with the most naive version of the convex optimization problem that can be meaningful. 20 AI-Assisted Discovery of Convex Relaxations via Dual Agents After this you have an iterative loop

[5] [10]

Then, create {nextversion} folder and copy the contents from the previous folder

Read the most recent version folder. Then, create {nextversion} folder and copy the contents from the previous folder

[6] [11]

The proposal should not be something like a hyperparameter tweak; we will enhance the hyperparameters after the convex program has converged

Come up with a novel proposal that improves upon the previous implementation. The proposal should not be something like a hyperparameter tweak; we will enhance the hyperparameters after the convex program has converged

[7] [12]

rigorous

After you come up with a proposal, you have to generate a "rigorous" proof that the constraint indeed holds. For an example see Lemma 3,4,5 in the convex optimization problem of White and how it is related to the convex optimization problem in section 5

[8] [13]

Name it as rigorousproof.md

Store the proof in the current version folder. Name it as rigorousproof.md

[9] [14]

It will be in the same folder, verdict.md

Now this is the important: you should be idle until the theorist agent reads your proof and gives a verdict. It will be in the same folder, verdict.md. If the verdict is VALID, it means your proposed proof is rigorous and makes sense. If the verdict is INVALID, it means your proposed proof has a flaw

[10] [15]

IF the verdict was VALID, implement the constraint in the convex problem

[11] [16]

should I keep going?

IF the verdict was INVALID, go to 2 and propose a different constraint that makes mathematical sense. *** THINGS TO CONSIDER *** - A validation should take less than 10 minutes. Don’t heavily optimize the parameter space (split the original problem into too many different convex optimization problems) or increase the problem parameters too much. Our job i...

work page arXiv