🤖 machine learning

Invariant Discovery for Networked Systems

This paper introduces Autogram, a system that combines AI-driven grammar discovery with statistics-driven search to automatically generate auditable, formally guaranteed invariants for networked systems, effectively overcoming the limitations of manual writing and existing automatic miners in handling real-world data noise.

Original authors: Hongyu Hè, Alexander Krentsel, Sylvia Ratnasamy, Maria Apostolaki

Published 2026-07-28

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Hongyu Hè, Alexander Krentsel, Sylvia Ratnasamy, Maria Apostolaki

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine the internet not as a cloud of magic, but as a massive, bustling city of data. In this city, billions of tiny packets of information zip along roads, stop at traffic lights, and pile up in warehouses. To keep this city running, engineers need to know the "rules of the road." These rules are called invariants. Think of them as the unbreakable laws of physics for the network: "The number of cars leaving a parking lot must equal the number of cars entering, plus or minus a tiny bit of error." If these rules are broken, it means a traffic light is stuck, a road is closed, or someone is stealing data.

For a long time, finding these rules was like trying to write a dictionary for a language nobody had ever spoken before. Engineers had to sit down and manually write every single rule by hand, guessing how the data should behave. It was slow, boring, and required a super-expert who knew both computer science and the specific quirks of their network. Recently, people tried to use computers to learn these rules automatically, but those computers were too rigid; they demanded perfect, exact matches and threw away anything that wasn't 100% perfect, even though real-world data is always a little messy. Then, people started using super-smart AI (Large Language Models) to help, but those AIs are like creative writers who sometimes make things up (hallucinate) and can't prove their work is true. The big question was: How do we get the creativity of AI without the risk of it making things up?

This paper introduces a new system called Autogram that solves this puzzle by splitting the job in half. The authors realized that while AI is great at guessing what kind of rules might exist, it is terrible at proving they are true. So, they built a system where the AI acts as a "grammar architect." It looks at the names of the data points (like "router_A_output" or "link_B_traffic") and suggests a list of possible rule structures, like a menu of potential sentences. It never actually claims a rule is true; it just says, "Here are some sentences that could make sense."

Once the AI draws up this menu, a strict, boring, and perfectly logical computer engine takes over. This engine checks every single sentence on the menu against the real data. It uses math to see if the rule holds up, even if it's not perfect. It allows for a little bit of wiggle room (called "softness") because real data is noisy, but it demands statistical proof before accepting a rule. If the AI suggests a rule that looks cool but doesn't fit the data, the logical engine rejects it immediately. If the AI misses a rule, the system can ask the AI to rewrite the menu and try again.

The researchers tested Autogram on real-world internet traffic data from public networks and a massive production network used by a company. They found that Autogram could rediscover every single rule that human experts had already written down, but it also found many new, useful rules that no one had ever noticed before. For example, it found that traffic leaving a router was consistently about 2% less than expected, which turned out to be a specific, explainable quirk of how the data was counted, not a disaster. While previous tools that demanded perfect accuracy missed almost all of these rules, Autogram found them all.

The paper shows that this approach works well and is fast, taking only about ten minutes to analyze a network with hundreds of routers. However, the authors are careful to note that this isn't a magic wand that solves everything yet. The system still relies on the AI to guess the right "menu" of rules, and if the data labels are wrong, the AI might get confused. They also point out that the system can't yet combine simple rules to create complex, brand-new structures on its own. But, they suggest, this is a promising step toward a future where computers can help us discover the hidden laws of our digital world, making the internet safer and more reliable without needing a human to write every single rule from scratch.

Technical Summary: Autogram for Invariant Discovery in Networked Systems

Problem Definition

Network invariants—relations expected to hold among measured signals—are foundational for network verification, traffic generation, telemetry imputation, and input validation. However, deriving these invariants for specific systems is notoriously difficult. It requires rare expertise in both formal logic and networking, and the process is labor-intensive and error-prone.

Existing automatic invariant mining methods face two critical limitations:

Grammar Dependency: They require a human expert to author the "grammar" of admissible invariants (the set of production rules defining which relations are expressible). This grammar must encode semantic knowledge (e.g., variable types, locality groupings, $n$ -ary aggregations) that raw data does not reveal.
Hard vs. Soft Rules: Most existing miners learn only "hard" rules that hold exactly on every observation. Real-world network data contains inherent noise (aleatoric uncertainty) and systematic bias (e.g., counter offsets), meaning the most valuable invariants are "soft"—they hold within a tolerance on most, but not all, observations.

While Large Language Models (LLMs) possess the semantic reasoning to infer such grammars from variable names and metadata, they are non-deterministic and prone to hallucinations, making their direct output unsuitable for auditable, guaranteed system checks.

Methodology: Autogram

The authors propose Autogram, a system that partitions the invariant discovery problem into two distinct phases: an AI-driven "grammar discovery" phase and a statistics-driven "search" phase. This division allows the non-deterministic power of LLMs to assist without compromising the formal guarantees of the final output.

1. Architecture and Workflow

LLM Proposer (Non-Deterministic): The LLM acts solely as a grammar inducer. It takes variable names and rich metadata (topology, role, vendor annotations) as input and proposes a bounded, typed grammar. Crucially, the LLM never asserts that a specific relation holds; it only defines the hypothesis space.
Deterministic Engine: Once the grammar is induced, a deterministic engine takes over:
- Exhaustive Enumeration: It enumerates the entire bounded hypothesis space defined by the grammar.
- Logical Pruning: A solver screens candidates to remove trivial truths, self-contradictions, and logical redundancies.
- Statistical Validation: A statistical test evaluates candidates against the data. Unlike hard miners, Autogram accepts "soft" invariants. It calculates a per-candidate tolerance based on the residuals of the data (using conformal prediction bands) rather than a fixed global threshold.
Calibration: To avoid overfitting or circular reasoning, the system's generic acceptance thresholds are calibrated on synthetic proxy datasets with planted relations and injected noise, never on the actual invariants the system hopes to recover.
Re-induction: If the system fails to recover known invariants (on a held-out split), it triggers a re-induction step where the LLM proposes a strictly more expressive grammar (e.g., adding higher-degree terms or aggregations).

2. Key Guarantees

By confining the LLM to grammar proposal and keeping the search deterministic, Autogram provides three key properties:

Determinism and Exhaustiveness: Given a grammar, the system enumerates the space identically on every run, ensuring reproducibility and auditability.
Soundness: Every returned invariant is non-trivial (verified by a solver) and clears a conservative confidence bar.
Monotone Completeness: The system is guaranteed to find any unknown invariant that holds at least as often, on at least as much data, as a known invariant the operator already trusts.

Key Contributions

Decoupling Semantics from Search: The paper demonstrates that the "grammar" (semantic judgment) and the "search" (statistical verification) can be separated. This allows LLMs to handle the semantic burden of defining the hypothesis space while statistical methods handle the verification.
Soft Invariant Discovery: Autogram is designed to discover soft invariants with data-driven tolerances, addressing the reality that network measurements are noisy and often contain systematic offsets.
Metadata-Driven Grammar Induction: The system leverages existing operator metadata (variable names, topology, roles) to induce grammars, removing the need for manual grammar authoring.
Auditable AI Integration: It provides a framework for integrating non-deterministic AI into safety-critical systems by ensuring the AI only shapes the search space, while the data and solvers determine the final results.

Results

The authors evaluated Autogram on public WAN datasets (Abilene, GEANT) and a production WAN ("WAN prod").

Recovery of Known Invariants: On public datasets, Autogram recovered 100% of the expert-derived invariants reported by the CrossCheck system. In contrast, a state-of-the-art baseline (NetNomos), restricted to exact rules and a hand-authored grammar, recovered less than 20% of these invariants.
Discovery of New Relations: Autogram discovered useful relations not previously recorded, such as topology presence symmetry and demand conservation laws.
Diagnostic Capability: The system successfully identified systematic offsets (e.g., a consistent ~2% deficit in traffic origination reports compared to demand matrices) rather than discarding them as noise. This highlights the utility of soft invariants for diagnostics.
Efficiency and Scalability: On a production network with ~100 routers and ~1,000 links, Autogram discovered 41 invariants in ten minutes. Runtime scales gently with network size.
Expressivity: Autogram achieved full recall with 101 rules on the GEANT dataset, whereas NetNomos required 1,645 rules (many of which were vacuous) to achieve partial recall.

Significance and Claims

The paper positions Autogram as a "promising step toward open-ended discovery." It argues that the primary bottleneck in invariant discovery has shifted from searching for relations to defining the language in which they can be expressed. By using LLMs to propose grammars based on metadata, Autogram automates this bottleneck.

The authors are modest about the current state of the system, acknowledging two boundaries:

Composability: Autogram cannot yet compose discovered invariants into relational structures that none of them expresses in isolation.
Decidability Ceiling: The expressiveness of the system is capped by the decidability of the underlying solvers, leaving non-linear structures largely unexplored.

The paper concludes that while Autogram cannot yet achieve fully open-ended discovery without human intervention, it successfully bridges the gap between the semantic reasoning of LLMs and the rigorous guarantees required for network operations, enabling the recovery of expert-derived invariants with high coverage and low false positives.