TLDR: MEC3O is a multi-expert AI system that predicts code time complexity. It assigns different Large Language Models (LLMs) as experts to specific complexity classes (e.g., O(1), O(n)). These experts then engage in structured debates, sharing and refining their predictions. A weighted consensus mechanism, which prioritizes expert opinions and their confidence, integrates these predictions to deliver more accurate results than single LLMs or traditional multi-agent debate systems, even outperforming some commercial LLMs.
Understanding how quickly a piece of code will run as its input grows is crucial for building efficient software and analyzing algorithms. This is known as predicting code time complexity. While large language models (LLMs) have made incredible strides in many areas of code analysis, they often struggle with accurately predicting time complexity, especially for certain classes of complexity. A recent study highlighted that no single LLM excels at every complexity class; instead, each model tends to have strengths in particular areas.
Addressing this challenge, researchers have introduced MEC3O, a novel multi-expert consensus system designed to significantly improve code time complexity prediction. MEC3O stands for Multi-Expert Consensus for Code Time Complexity Prediction, and it takes inspiration from multi-agent debate frameworks, but with a clever twist.
How MEC3O Works: A Collaborative Intelligence Approach
The core idea behind MEC3O is to leverage the individual strengths of different LLMs. Instead of relying on one model to be a jack-of-all-trades, MEC3O turns LLMs into specialized ‘experts’ for specific time complexity classes. Imagine a team of specialists, each brilliant in their own field, coming together to solve a complex problem.
Here’s a simplified breakdown of MEC3O’s three main steps:
1. Expertise Assignment: First, MEC3O identifies which LLM performs best for each of the seven defined complexity classes: O(1) (constant), O(logn) (logarithmic), O(n) (linear), O(nlogn) (linearithmic), O(n2) (quadratic), O(n3) (cubic), and O(2n) (exponential). Once identified, that LLM is assigned as the expert for that specific class and receives specialized instructions tailored to its area of expertise. This ensures that each expert is primed to focus on the patterns and characteristics relevant to its assigned complexity.
2. Multi-Expert Debate: After receiving their specialized instructions, these experts generate initial predictions for a given code snippet. Crucially, they then share their initial opinions and rationales with each other. If an expert notices a logical flaw or an overlooked detail in its own reasoning after reviewing others’ outputs, it can revise its prediction. This structured exchange acts as a cross-checking mechanism, reducing the risk of errors that a single model might miss. A unique aspect is ‘restricted assents,’ where experts can choose to ignore contradictory suggestions from non-experts if they are highly confident in their own class knowledge, preventing correct but minority opinions from being diluted.
3. Weighted Consensus: Once the debate phase concludes and opinions have converged, MEC3O integrates the final predictions from all experts using a ‘Weighted Expertise-Confidence Consensus’ (WECC) function. This function doesn’t just take a simple majority vote. Instead, it gives more weight to experts who are predicting within their assigned class and also considers each expert’s confidence in its prediction. This intelligent weighting ensures that the final decision is robust and reflects the most reliable expert insights, rather than being swayed by potentially incorrect majority opinions or the biases of a single ‘judge’ model.
Overcoming Common LLM Challenges
MEC3O directly addresses several limitations of existing LLM approaches. Single LLMs often suffer from ‘Degeneration-of-Thought’ (DoT), where they get locked into an initial line of reasoning and fail to reconsider, even when faced with contradictory evidence. Traditional multi-agent debate systems, while an improvement, can still fall prey to incorrect majority opinions or over-reliance on a single judge model, which might introduce its own biases.
By assigning explicit expertise and using a weighted consensus, MEC3O allows specialized experts to challenge locked-in errors and ensures that correct minority opinions can prevail when appropriate. This design enhances robustness and leverages the diversity of LLMs more effectively.
Also Read:
- LiveOIBench: A New Benchmark for LLMs in Competitive Programming
- Assessing the Spatial Limits of LLM Reasoning with RegexPSPACE
Impressive Results
Experiments conducted on the CodeComplex dataset demonstrated that MEC3O significantly outperforms all open-source baselines, achieving at least 10% higher accuracy and macro-F1 scores. What’s more, MEC3O proved highly competitive with powerful commercial LLMs like GPT-4o-mini and even GPT-4o, outperforming GPT-4o-mini in macro-F1 scores on average. This suggests that a well-orchestrated collaboration of smaller, open-source LLMs can achieve performance comparable to, or even better than, much larger single proprietary models.
The findings highlight the immense value of combining specialized instructions, multi-expert collaboration, and a sophisticated weighted consensus strategy for complex tasks like code time complexity prediction. You can read the full research paper here.
