Networks of Networks: Complexity Class Principles Applied to Compound AI Systems Design

Jared Quincy Davis, Boris Hanin, Lingjiao Chen, Peter Bailis, Ion Stoica, Matei ZahariaarXiv 2024 · OpenReview

Abstract

As practitioners seek to surpass the current reliability and quality frontier of monolithic models, Compound AI Systems consisting of many language model inference calls are increasingly employed. In this work, we construct systems, which we call Networks of Networks (NoNs) organized around the distinction between generating a proposed answer and verifying its correctness, a fundamental concept in complexity theory that we show empirically extends to Language Models (LMs). We introduce a verifier-based judge NoN with K generators, an instantiation of "best-of-K" or "judge-based" compound AI systems. Through experiments on synthetic tasks such as prime factorization, and core benchmarks such as the MMLU, we demonstrate notable performance gains. For instance, in factoring products of two 3-digit primes, a simple NoN improves accuracy from 3.7% to 36.6%. On MMLU, a verifier-based judge construction with only 3 generators boosts accuracy over individual GPT-4-Turbo calls by 2.8%. Our analysis reveals that these gains are most pronounced in domains where verification is notably easier than generation—a characterization which we believe subsumes many reasoning and procedural knowledge tasks.

Introduction

Current advancements in Large Language Models (LLMs) are increasingly hitting a plateau in monolithic performance. To push past these boundaries, researchers are turning to Compound AI Systems—architectures that leverage multiple inference calls to solve complex problems. However, the design of these systems often lacks a formal theoretical foundation. This paper proposes "Networks of Networks" (NoNs), a design principle rooted in classical complexity theory, specifically the asymmetry between the difficulty of generating a solution and the ease of verifying a "witness" or proof.

The Verifier-Based Judge (VBJ) Architecture

The core of our approach is the Verifier-Based Judge (VBJ) system. In this setup, a query is sent to $K$ independent generator calls. Each generator produces both an answer and an explanatory "witness." These pairs are then evaluated by a separate "verifier" or judge model. The system returns the first answer accepted by the judge; if none are accepted, the system returns a random answer from the set.

The performance of this system is governed by three primary metrics:

  1. Completeness ($c$): The probability the judge correctly accepts a valid answer.
  2. Soundness ($s$): The probability the judge correctly rejects an invalid answer.
  3. Generation Difficulty ($r$): The baseline probability of a single generator finding the correct answer.

Empirical Validation: Prime Factorization

To test the limits of the generation-verification asymmetry, we utilized a 3-digit prime factorization task. Factorization is a classic example of a problem that is computationally difficult to solve but trivial to verify through multiplication.

Table 2: Performance on 3-digit factorization and component accuracy metrics showing high verification success.

As shown in the results, a monolithic GPT-4o call achieves only 3.7% accuracy. However, by employing a VBJ system with $K=10$, accuracy scales to 36.6%. The high verification task accuracy (90.1%) confirms that the model is significantly better at checking factors than finding them, validating the core NoN hypothesis.

Domain-Specific Performance on MMLU

We further evaluated the NoN approach across the 57 subjects of the MMLU benchmark. While the overall gain was 2.8% (moving from 81.2% to 84.0% with $K=3$), the benefits were not uniform. The system excels in "procedural" or reasoning-heavy domains where a logical path can be verified.

Table 5: MMLU subjects showing the highest performance improvements using the VBJ approach.

In subjects like Abstract Algebra, Formal Logic, and High School Math, we observed gains exceeding 8%. Conversely, in subjects relying on declarative knowledge or factual retrieval—such as Geography or World Religions—the VBJ approach yielded negligible or even slightly negative results. This suggests that when the judge has no independent way to verify a fact beyond what the generator provides, the "asymmetry" disappears.

Conclusion and Practitioner Takeaways

Our findings suggest that the efficacy of Compound AI Systems is deeply tied to the verifiability of the task. For ML practitioners, we offer several key takeaways:

  • Assess Verification Complexity: Before scaling inference calls, determine if the task allows for easier verification than generation.
  • The Simple Test: Measure the completeness and soundness of a potential verifier on a small sample to predict the potential ROI of increasing $K$.
  • Witness Format: The quality of the explanation (the "witness") is critical; a verifier can only be as good as the evidence it is given to judge.

By applying these complexity-class principles, developers can design more efficient and reliable multi-call AI systems that target the specific reasoning strengths of modern language models.

Summary updated

Abstract

As practitioners seek to surpass the current reliability and quality frontier of monolithic models, Compound AI Systems consisting of many language model inference calls are increasingly employed. In this work, we construct systems, which we call Networks of Networks (NoNs) organized around the distinction between generating a proposed answer and verifying its correctness, a fundamental concept in complexity theory that we show empirically extends to Language Models (LMs). We introduce a verifier-based judge NoN with K generators, an instantiation of "best-of-K" or "judge-based" compound AI systems. Through experiments on synthetic tasks such as prime factorization, and core benchmarks such as the MMLU, we demonstrate notable performance gains. For instance, in factoring products of two 3-digit primes, a simple NoN improves accuracy from 3.7\% to 36.6\%. On MMLU, a verifier-based judge construction with only 3 generators boosts accuracy over individual GPT-4-Turbo calls by 2.8\%. Our analysis reveals that these gains are most pronounced in domains where verification is notably easier than generation--a characterization which we believe subsumes many reasoning and procedural knowledge tasks, but doesn't often hold for factual and declarative knowledge-based settings. For mathematical and formal logic reasoning-based subjects of MMLU, we observe a 5-8\% or higher gain, whilst no gain on others such as geography and religion. We provide key takeaways for ML practitioners, including the importance of considering verification complexity, the impact of witness format on verifiability, and a simple test to determine the potential benefit of this NoN approach for a given problem distribution. This work aims to inform future research and practice in the design of compound AI systems.
BibTeX
@misc{davis2024networks,
  author = {Jared Quincy Davis and Boris Hanin and Lingjiao Chen and Peter Bailis and Ion Stoica and Matei Zaharia},
  title = {{Networks of Networks: Complexity Class Principles Applied to Compound AI Systems Design}},
  year = {2024},
  eprint = {2407.16831},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2407.16831},
}
Figure