\n ## Multi-Plot Performance Analysis: Algorithm Timing vs. Problem Parameters ### Overview The image is a composite of four line charts (labeled a, b, c, d) comparing the execution timing (in seconds) of seven different algorithms or methods across varying problem parameters. All plots share a common y-axis ("Timing (in s)") on a logarithmic scale (10^-1 to 10^4) and a common red dashed horizontal line indicating a "Timeout" at 10^4 seconds. The plots analyze scalability with respect to the number of inputs, layer width, satisfiability margin, and network depth. ### Components/Axes * **Common Y-Axis:** Label: "Timing (in s)". Scale: Logarithmic, ranging from 10^-1 (0.1 s) to 10^4 (10,000 s). * **Common Timeout Line:** A red dashed horizontal line at y = 10^4 seconds, labeled "Timeout" in red text at the right end of each plot. * **Legend (Present in all plots, top-left):** Lists seven data series with corresponding colors: * BaBSB (Blue) * BaB (Orange) * BaB-ER (Green) * reluplex (Red) * MIPplanet (Purple) * Planet (Brown) * BlackBox (Pink) * **Subplot Titles/Captions (Below each plot):** * (a) Number of inputs * (b) Layer width * (c) Margin * (d) Network depth ### Detailed Analysis #### **Subplot (a): Number of inputs** * **X-Axis:** Label: "Number of inputs". Scale: Logarithmic, with major ticks at 10^0 (1), 10^1 (10), 10^2 (100), 10^3 (1000). * **Trends & Data Points:** * **General Trend:** All algorithms show increasing timing as the number of inputs grows. The increase is roughly linear on the log-log plot for most, suggesting a polynomial time complexity relationship. * **BaBSB (Blue):** Starts near 10^0 s for 1 input. Increases steadily, crossing 10^1 s around 10 inputs, 10^2 s around 100 inputs, and approaches but does not reach the timeout at 1000 inputs (~5x10^3 s). * **BaB (Orange):** Follows a very similar path to BaBSB, nearly overlapping it. * **BaB-ER (Green):** Starts slightly higher than BaBSB/BaB. Increases more steeply, crossing 10^2 s before 100 inputs and hitting the timeout line (10^4 s) at approximately 200-300 inputs. * **reluplex (Red):** Starts the lowest (~2x10^-1 s for 1 input). Increases very steeply, crossing all other lines and hitting the timeout at approximately 50-60 inputs. * **MIPplanet (Purple):** Starts around 10^0 s. Increases at a moderate rate, crossing 10^2 s around 100 inputs and hitting the timeout at approximately 500-600 inputs. * **Planet (Brown):** Starts near 10^0 s. Increases similarly to MIPplanet but slightly slower, hitting the timeout at approximately 800-900 inputs. * **BlackBox (Pink):** Starts the highest (~5x10^0 s for 1 input). Increases at the slowest rate, remaining below 10^2 s even at 1000 inputs. #### **Subplot (b): Layer width** * **X-Axis:** Label: "Layer Width". Scale: Logarithmic, with major ticks at 10^0 (1), 10^1 (10), 10^2 (100). * **Trends & Data Points:** * **General Trend:** Timing generally increases with layer width, but the scaling behavior varies significantly between algorithms. * **BaBSB (Blue) & BaB (Orange):** Show a relatively gentle increase. At width=1, timing is ~10^0 s. At width=100, timing is ~10^2 s. * **BaB-ER (Green):** Increases more sharply than BaBSB/BaB, hitting the timeout at a width of approximately 30-40. * **reluplex (Red):** Shows the steepest increase, hitting the timeout at a width of approximately 5-6. * **MIPplanet (Purple):** Increases steeply, hitting the timeout at a width of approximately 20-25. * **Planet (Brown):** Increases at a rate between BaBSB and MIPplanet, hitting the timeout at a width of approximately 50-60. * **BlackBox (Pink):** Shows a very gentle, almost flat increase, remaining around 10^1 s across the entire range of widths. #### **Subplot (c): Margin** * **X-Axis:** Label: "Satisfiability margin". Scale: Logarithmic, with major ticks at 10^-1 (0.1), 10^0 (1), 10^1 (10), 10^2 (100). * **Additional Annotations:** Text labels at the bottom: "SAT / False" (left of 10^0) and "UNSAT / True" (right of 10^0). * **Trends & Data Points:** * **General Trend:** This plot shows non-monotonic behavior. Timing often decreases as the margin increases from very small values (10^-1) to around 1 (the SAT/UNSAT boundary), then increases again for larger margins. * **BaBSB (Blue) & BaB (Orange):** Show a "U-shaped" curve. Minimum timing (~2-3x10^0 s) occurs near margin=1. Timing rises to ~10^2 s at both margin=0.1 and margin=100. * **BaB-ER (Green):** Similar U-shape but with higher overall timing. Minimum (~10^1 s) near margin=1. Hits timeout at margin=100. * **reluplex (Red):** Shows a very sharp V-shape. Minimum timing (~10^0 s) at margin=1. Increases extremely steeply on both sides, hitting timeout at margin=0.3 and margin=3. * **MIPplanet (Purple):** Shows a U-shape. Minimum (~10^1 s) near margin=1. Hits timeout at margin=100. * **Planet (Brown):** Shows a U-shape. Minimum (~10^1 s) near margin=1. Hits timeout at margin=100. * **BlackBox (Pink):** Shows a relatively flat, high timing (~10^2 s) across the entire margin range, with a slight dip near margin=1. #### **Subplot (d): Network depth** * **X-Axis:** Label: "Layer Depth". Scale: Linear, with major ticks at 2, 3, 4, 5, 6. * **Trends & Data Points:** * **General Trend:** Timing increases with network depth for all algorithms. The increase appears exponential (linear on the semi-log plot). * **BaBSB (Blue) & BaB (Orange):** Start at ~10^0 s for depth=2. Increase to ~10^2 s at depth=6. * **BaB-ER (Green):** Starts near BaBSB at depth=2. Increases more steeply, hitting timeout at depth=5. * **reluplex (Red):** Starts lowest at depth=2 (~2x10^-1 s). Increases the most steeply, hitting timeout at depth=4. * **MIPplanet (Purple):** Starts around 10^0 s at depth=2. Increases steeply, hitting timeout at depth=5. * **Planet (Brown):** Starts around 10^0 s at depth=2. Increases at a rate similar to MIPplanet, hitting timeout at depth=5. * **BlackBox (Pink):** Starts highest at depth=2 (~10^1 s). Increases at the slowest rate, reaching ~10^3 s at depth=6. ### Key Observations 1. **Performance Hierarchy:** reluplex is consistently the fastest for very small/simple problems (low inputs, narrow layers, margin=1, shallow depth) but scales the worst, hitting timeouts earliest. BlackBox is consistently the slowest for small problems but scales the best, often being the only algorithm not to timeout for large/complex instances. 2. **Critical Parameter:** The "Satisfiability margin" plot (c) reveals a critical performance sweet spot at margin=1 (the SAT/UNSAT boundary) for most algorithms, where timing is minimized. 3. **Scalability Trends:** BaBSB and BaB demonstrate the most robust and predictable polynomial scaling across inputs, width, and depth. BaB-ER, MIPplanet, and Planet show intermediate scaling, often hitting timeouts for large parameters. 4. **Timeout Clusters:** In plots (a), (b), and (d), algorithms tend to hit the timeout in a consistent order: reluplex first, followed by BaB-ER/MIPplanet/Planet, then BaBSB/BaB, with BlackBox often not timing out. ### Interpretation This composite chart provides a comprehensive scalability analysis of neural network verification or analysis algorithms. The data suggests a fundamental trade-off between raw speed on small instances and robustness to problem size. * **Algorithm Selection Guidance:** The choice of algorithm should be heavily informed by the expected problem scale. For quick checks on small networks, reluplex is optimal. For large-scale, industrial-sized networks, BlackBox, despite its high constant overhead, becomes the only viable option. BaBSB/BaB offer a balanced middle ground. * **Problem Difficulty Insight:** The pronounced minimum at margin=1 in plot (c) indicates that problems near the decision boundary (where the property is barely true or false) are computationally easiest for these solvers. Problems with large margins (clearly true or false) are harder, likely because they require exploring a larger search space to confirm the margin. * **Architectural Sensitivity:** The steep increases in plots (b) and (d) show that algorithm performance is highly sensitive to network architecture (width and depth). This implies that verifier-friendly network design (e.g., keeping layers narrow and shallow) is crucial for tractable analysis. * **Underlying Methods:** The performance profiles hint at the underlying methods. reluplex's steep scaling suggests a simplex-like method that struggles with dimensionality. BlackBox's flat scaling suggests a sampling or optimization-based approach with high overhead but good scalability. The BaB family (BaBSB, BaB, BaB-ER) likely uses branch-and-bound, with BaB-ER incorporating an extra refinement step that adds overhead but may improve precision.