ACM HotNets 2026

AutogramInvariant Discovery for Networked Systems

Hongyu Hè1,* Alexander Krentsel2,* Sylvia Ratnasamy2 Maria Apostolaki1

1 Princeton University2 UC Berkeley / Google

* Equal contribution

Paper PDF Slides PDF arXiv BibTeX

Discovering network invariants from noisy telemetry by pairing AI grammar design with deterministic search and validation.

Presentation & demo

2-minute paper intro

System demo

AI defines the hypothesis space, and logic and statistics validate every invariant.

Network invariants are the relations that must hold among network signals, such as traffic counters across routers that should roughly agree. Autogram discovers these invariants to catch corrupted data before a controller acts on it, pairing an AI agent that designs the search grammar with a deterministic engine that tests every candidate against noisy measurements.

  1. 1

    Confine the hypothesis space

    Signal names and metadata explain what each counter measures and where it belongs. An AI agent turns that semantic context into a compact grammar that defines the hypothesis space of candidate invariants.

  2. 2

    Validate candidates deterministically

    A deterministic pipeline systematically explores every candidate in the grammar. The Z3 solver prunes trivial and redundant relations, while statistical checks fit a noise tolerance and test whether each surviving candidate holds reliably on unseen telemetry.

  3. 3

    Broaden the grammar when needed

    Missing a known invariant signals that the grammar is too narrow. Without revealing known invariants, the agent expands the language to discover more diverse candidates.

AI agent is only used to discover the grammar that confine the search space, leaving the search and validation processes deterministic.

Abstract

Network invariants support applications from verification to traffic generation, telemetry imputation, and input validation. Writing these rules by hand requires expertise in both networking and formal logic. Testing all combinations of network variables is impractical at scale. Existing tools depend on expert-written grammars and exact rules that miss invariants obscured by noise.

Autogram uses a large language model to construct a compact grammar from variable names and metadata. The grammar defines which relations the system can express and test. A deterministic engine searches that space, removes trivial or contradictory candidates with a logical solver, and evaluates the remaining rules on held-out telemetry. When the search misses trusted invariants, Autogram asks the model to expand the grammar and repeats the checks.

Autogram produces readable invariants with measured tolerances and hold rates. For a fixed grammar and dataset, the search is reproducible and exhaustive. Our prototype recovered expert-derived invariants with full recall and low false positives in evaluations on public and production WAN telemetry.

BibTeX

@inproceedings{he2026autogram,
  title     = {Invariant Discovery for Networked Systems},
  author    = {Hè, Hongyu and Krentsel, Alexander and
               Ratnasamy, Sylvia and Apostolaki, Maria},
  booktitle = {The 25th ACM Workshop on Hot Topics in Networks},
  series    = {HotNets '26},
  year      = {2026},
  publisher = {Association for Computing Machinery},
  doi       = {10.1145/3847290.3859952},
  url       = {https://doi.org/10.1145/3847290.3859952}
}