AI-Assisted Discovery of Convex Relaxations via Dual Agents

This paper, “AI-Assisted Discovery of Convex Relaxations via Dual Agents,” represents a significant pivot in how we apply large language models (LLMs) to pure mathematics. While previous work has focused on using LLMs as “searchers” for counterexamples or extremal constructions (providing upper bounds), this research tackles the harder, complementary problem: proving lower bounds via convex relaxations.

What Happened

The core innovation is a dual-agent framework. One agent (the “primal” agent) searches for functions that violate a conjectured inequality, attempting to push an upper bound higher. The second agent (the “dual” agent) attempts to construct a convex relaxation—a mathematical proof technique that yields a lower bound for the inequality’s constant. By having these agents compete and share information, the system can iteratively tighten the gap between the upper and lower bounds, effectively proving the sharp constant.

The paper demonstrates this on classic inequalities (e.g., Hardy-type inequalities), showing that the dual agent can discover non-trivial convex relaxations that were previously unknown or required significant human insight. This is not brute-force computation; it is a structured, adversarial search over proof strategies.

Why It Matters

This work matters for three reasons. First, it addresses a fundamental asymmetry in AI-assisted mathematics. Finding counterexamples is computationally cheap (check one function). Proving a bound holds for all functions is exponentially harder. By automating the construction of convex relaxations, the paper opens a path toward AI systems that can generate complete proofs, not just conjectures.

Second, the dual-agent architecture is a practical template. It mirrors the “generator-discriminator” dynamic seen in GANs, but applied to formal logic. This suggests that for many problems in optimization and analysis, the most productive role for an LLM is not as a single oracle, but as a component in a competitive ecosystem of agents.

Third, convex relaxations are the backbone of modern optimization (semidefinite programming, linear programming relaxations). If LLMs can discover novel relaxations for mathematical inequalities, they may soon discover novel relaxations for NP-hard combinatorial problems or machine learning training objectives.

Implications for AI Practitioners

For practitioners, the immediate takeaway is architectural. The paper demonstrates that a single LLM call is rarely sufficient for complex reasoning tasks. Instead, you need:

• Role separation: Give agents distinct, adversarial objectives (primal vs. dual).
• Shared memory: Allow agents to see each other’s partial results to guide their search.
• Formal verification: The dual agent’s output must be verifiable (convexity is checkable), not just plausible.

This is a blueprint for building LLM systems that can tackle problems requiring both creativity and rigorous proof—a combination that has historically been the exclusive domain of human mathematicians.

Key Takeaways

• Dual-agent frameworks outperform single-agent search for proving lower bounds in mathematical inequalities, addressing a key limitation of prior AI-assisted math work.
• Convex relaxations are a promising target for LLM discovery because they are both expressive (capture many proofs) and verifiable (convexity is algorithmically checkable).
• Adversarial collaboration between LLM agents (primal vs. dual) can tighten the gap between upper and lower bounds, effectively automating parts of the proof discovery process.
• Practitioners should adopt role-separated, memory-sharing agent architectures for any task requiring both creative generation and rigorous constraint satisfaction.