mlsanityData to 14 Oct 2026

AI-Assisted Discovery of Convex Relaxations via Dual Agents

arXiv 2606.31182 ↗First posted 30 Jun 2026cs.AIcited by 2

On the map: LLM agents and tool use → General LLM agent frameworks and benchmarks

Abstract (arXiv)

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 citettao2025alphaevolve - the first autocorrelation inequality (C6.2) and the ErdHos minimum-overlap constant (C6.5) - we improve the certified lower bounds from 1.28 to 1.2937 and from 0.379005 to 0.37912, respectively.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Placed in General LLM agent frameworks and benchmarks, one of 16 directions in LLM agents and tool use. Builds on 17 of its 52 references that are in the map. First posted on arXiv 30 Jun 2026.

Builds on

17 of 52 references.

References · 17

  1. 2023SWE-bench: Can Language Models Resolve Real-World GitHub Issues?cited by 3,373
  2. 2024LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Codecited by 2,004
  3. 2025AlphaEvolve: A coding agent for scientific and algorithmic discoverycited by 867
  4. 2016CVXPY: A Python-Embedded Modeling Language for Convex Optimizationcited by 641
  5. 2026Learning to Discover at Test Timecited by 115
  6. 2025Winning Gold at IMO 2025 with a Model-Agnostic Verification-and-Refinement Pipelinecited by 82
  7. 2025A Self-Improving Coding Agentcited by 79
  8. 2025Mathematical exploration and discovery at scalecited by 77
  9. 2025ThetaEvolve: Test-time Learning on Open Problemscited by 64
  10. 2025LiveCodeBench Pro: How Do Olympiad Medalists Judge LLMs in Competitive Programming?cited by 55
  11. 2025Early science acceleration experiments with GPT-5cited by 41
  12. 2025APOLLO: Automated LLM and Lean Collaboration for Advanced Formal Reasoningcited by 35
5 more
  1. 2026First Proofcited by 32
  2. 2026Advancing Mathematics Research with AI-Driven Formal Proof Searchcited by 23
  3. 2026Structured Scaling of AI Discovery Across Diverse Scientific Domainscited by 21
  4. 2026130k Lines of Formal Topology in Two Weeks: Simple and Cheap Autoformalization for Everyone?cited by 18
  5. 2025SITA: A Framework for Structure-to-Instance Theorem Autoformalizationcited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Autonomous Mathematical Discovery in an Open-World Multi-Agent Environmentcited by 1
  2. 2026Learning to Design Convex Relaxations for Nonconvex Optimizationcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026The Condition-Number Barrier in Sparse Least Squares
  2. 2024Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexity
  3. 2025Learn to Relax with Large Language Models: Solving Constraint Optimization Problems via Bidirectional Coevolution
  4. 2026Distribution-Aware Algorithm Design with LLM Agents
  5. 2026Agentic Bayesian Optimization through Surrogate-Augmented Autoresearch
  6. 2026NC2C: Automated Convexification of Generic Non-Convex Optimization Problems
  7. 2026Markovian Nonconvex ADMM for Reinforcement Learning: Bellman-Resolvent Stability Beyond Smooth Blocks
  8. 2026Rate-Distortion Analysis of Compressed Query Delegation with Low-Rank Riemannian Updates