LLMs enable 67x speedup in 3-SAT via meta-optimization framework
New meta-optimization approach uses LLMs to rewrite its own evaluation criteria, achieving 67x speedup.
Researchers from the University of California San Diego and other institutions have published a paper formalizing scientific discovery as a meta-optimization problem, where not only the candidate solutions but also the evaluation criteria themselves are optimized. Their core innovation, 'consensus objective aggregation,' uses multiple LLMs to generate candidate objective functions, then combines them via correlation-weighted voting to produce a stable, self-correcting metric that evolves as understanding deepens. This addresses a key limitation of previous LLM-driven research automation, which focused only on exploring the hypothesis space while keeping the objective fixed.
The team tested their framework on algorithm discovery for 3-SAT (3-satisfiability), a classic NP-complete problem, using digital MemComputing machines as the underlying solver. By allowing the LLM-generated objective to guide the search for better algorithmic parameters, they reduced the baseline scaling with problem size N from O(N^2.51) to O(N^1.33) — a 67x speedup on the largest instances tested (with N up to 100 variables). The paper claims the framework is problem-agnostic and could be applied to other scientific domains, potentially accelerating drug discovery, material design, and more.
- Method uses LLMs to generate and combine objective functions via correlation-weighted voting (self-correcting).
- Applied to 3-SAT algorithm discovery, reduced scaling from N^2.51 to N^1.33, 67x faster on largest instances.
- Framework is problem-agnostic, designed to accelerate automated scientific discovery across domains.
Why It Matters
Shows LLMs can automate not just hypothesis testing but also the evolution of evaluation criteria, drastically accelerating optimization.