Technical Summary: Convergence Theory for Iterative LLM-Based Neural Architecture Search

1. Problem Statement

Neural Architecture Search (NAS) has recently shifted from predefined search spaces to using Large Language Models (LLMs) as open-ended generators of executable torch.nn.Module programs. While empirical studies (e.g., Khalid et al., Adhikari et al.) demonstrate that iteratively fine-tuning an LLM on its own successful generations improves both generation reliability and architecture quality, no formal convergence theory exists for this class of algorithms.

Key theoretical gaps addressed include:

• Does iterative LLM fine-tuning provably improve architecture quality?
• Under what conditions does the process converge?
• Why does "delta generation" (generating unified diffs) achieve higher valid-generation rates than full-code generation?
• What is the theoretical role of novelty filtering in preventing degenerate solutions (mode collapse)?
• How can the reliability of proxy-based rankings (using short training epochs) be quantified?

2. Methodology and Mathematical Framework

The authors model iterative LLM-NAS as a parametric Cross-Entropy (CE) method over executable programs. The framework establishes a formal link between the LLM fine-tuning process and the well-studied CE optimization algorithm.

Core Definitions

• Architecture Space ($\mathcal{A}$): The set of syntactically valid, executable Python programs defining a torch.nn.Module.
• Quality Function ($q$): Maps an architecture to its first-epoch validation accuracy on a fixed dataset.
• Elite Set ($E_\tau$): Architectures where $q(a) \geq \tau$.
• Iterative Process:
  1. Generate: Sample $N$ candidates from the current LLM distribution $p_{\theta_t}$.
  2. Evaluate & Filter: Select elite architectures that pass a MinHash–Jaccard novelty filter.
  3. Update: Fine-tune the LLM parameters $\theta$ using the union of the elite set and the static corpus (minimizing cross-entropy loss).

Theoretical Assumptions

The proofs rely on specific assumptions, notably:

• Regularity: Bounded quality, positive initial mass of elite architectures, and consistent estimation as sample size grows.
• Quality-Monotone Projection: The CE projection onto the parametric family (LLM) preserves or improves the mean quality of the distribution.
• Token-Error Model: A first-order Markov chain model for token errors (replacing the independent-token assumption) to analyze delta vs. full-code generation.
• Proxy Reliability: Assumes bivariate Normal distribution between proxy (short training) and full-training accuracies.

3. Key Contributions and Theoretical Results

The paper proves six main results:

A. Equivalence to Parametric CE (Theorem 1)

Iterative LLM fine-tuning on elite architectures is mathematically equivalent to the Cross-Entropy update restricted to the LLM's parametric family. The fine-tuning step minimizes the Kullback–Leibler (KL) divergence between the empirical distribution of elite samples and the LLM's generation distribution.

B. Monotone Quality Improvement (Theorem 2)

Under the stated assumptions, the expected architecture quality ($Q_t$) is monotonically non-decreasing across cycles, up to a finite-sample estimation error term $\epsilon_t = O(N^{-1/2})$.

C. Convergence to a Fixed Point (Theorem 3 & Corollary 4)

• The probability of generating an elite architecture ($C_t$) converges to a fixed point $C^*$ at a geometric rate: $C_t \geq 1 - (1 - \rho_0)^t$.
• LoRA Constraint: If the LLM is adapted via LoRA (Low-Rank Adaptation), the expressiveness of the parametric family is restricted. Consequently, the process converges to a plateau $C^* \leq 1$ rather than 1, explaining empirical observations of performance ceilings.

D. Delta Generation Advantage (Theorem 5 & Corollary 6)

Using a first-order Markov token-error model, the authors prove that delta generation (generating diffs) achieves a strictly higher valid-generation rate than full-code generation.

• The ratio of valid rates depends on the output length reduction factor $\alpha$ (where $L_\delta = \alpha L_{full}$).
• The theory predicts a ratio $> 1$, with a calibrated prediction of $\approx 2.23$ under specific parameters, though empirical results showed a ratio of $1.41$ (confirming the direction but undershooting the magnitude due to unmodeled long-range correlations).

E. Prevention of Mode Collapse (Theorem 7)

The application of a MinHash–Jaccard novelty filter ensures that the corpus remains "separated." Theoretically, this prevents the LLM from collapsing to a single architecture (mode collapse), maintaining a non-zero entropy in the generation distribution.

F. Closed-Form Proxy Reliability (Theorem 8)

The paper derives a closed-form relationship between the Signal-to-Noise Ratio (SNR) of the proxy task and the Spearman rank correlation ($\rho_S$) between proxy and full-training rankings:
$$\rho_S = \frac{6}{\pi} \arcsin\left(\frac{\rho_P(SNR)}{2}\right)$$
where $\rho_P(SNR) = (1 + SNR^{-1})^{-1/2}$.

• Diagnostic: A necessary condition for trustworthy proxy-based rankings is $\sigma^2_{arch} \gg \sigma^2_{noise}$ (high architectural variance relative to noise).
• Ceiling Effect: The theory explains why proxy reliability plateaus when SNR is low (e.g., in datasets with low architectural diversity).

4. Empirical Validation

The authors tested these theories against a 22-cycle experiment involving three LLMs (Mistral, Qwen, DeepSeek) and 3,300 generated architectures.

• Consistent Quantitative Predictions:
  • Monotone Quality: The smoothed mean quality trend was non-decreasing for all models.
  • Novelty: Novel architectures were admitted in every cycle, preventing mode collapse.
• Direction-of-Effect Consistency:
  • Elite Concentration: The concentration $C_t$ plateaued at 73–76%, consistent with the LoRA expressiveness ceiling (converging to $C^* < 1$).
  • Proxy Reliability: The ordering of Spearman correlations (Mistral > Qwen > DeepSeek) perfectly matched the SNR ranking. DeepSeek showed non-significant correlation, consistent with low SNR predictions.
• Deviations:
  • Delta Rate Ratio: Observed ratio (1.41) was lower than the calibrated theoretical prediction (2.23), attributed to format-invalid diffs and correlations beyond the first-order Markov model.
  • Qwen Correlation: The observed Spearman correlation (0.635) exceeded the bivariate Normal prediction (0.10) due to accuracy ceiling truncation, a limitation noted by the authors.

5. Significance and Claims

The paper claims to provide the first formal convergence guarantees for iterative LLM-based NAS. Its significance lies in:

1. Theoretical Unification: Identifying LLM-NAS as a parametric CE method, allowing the application of established optimization convergence theory.
2. Explaining Empirical Phenomena: Providing mathematical justification for why delta generation works better and why performance plateaus occur with LoRA.
3. Diagnostic Tool: Offering a closed-form formula to diagnose the reliability of proxy-based architecture rankings based on SNR, explaining previously observed but unexplained "ceiling effects."

The authors remain modest, noting that their empirical validation relies on a single existing dataset and that the theoretical bounds for LoRA-adapted models (convergence to $C^* < 1$) are conditional on expressiveness assumptions that are difficult to verify analytically. Future work is identified as extending convergence rates to low-rank constraints and handling truncated accuracy supports.