Dependency Geometry

What does a sequence forget?

A computation is not inherently a list. It is a collection of operations with constraints: some tasks must happen before others, while many may be independent. That structure determines the computation's available parallelism.

An execution turns this structure into a timeline. If two independent tasks $A$ and $B$ both feed a later task $C$, either

$$ A,;B,;C $$

or

$$ B,;A,;C $$

is a valid serial execution. Looking at only the first trace, however, we cannot tell whether $A$ truly had to precede $B$ or whether the scheduler merely chose that order. Serialization preserves what happened first, but not what had to happen first.

This research project develops an inverse theory of that information loss. It asks:

• How many dependency structures are compatible with one observed sequence?
• How much hidden parallelism can be inferred from ordering alone?
• If we observe repeated independent executions, how quickly do accidental orderings disappear?
• What makes some dependency structures much harder to recover than others?

Explore the project site · Read the revised paper · Browse the combined results

Mathematical picture

Let $P=(V,\prec_P)$ be a finite poset: $V$ is the set of operations and $x\prec_P y$ means that $x$ must complete before $y$. A serial trace $\pi=(v_1,\ldots,v_n)$ is a linear extension of $P$—a total ordering that respects every true dependency.

One trace usually leaves many possible dependency structures. Its inverse fiber is

$$ \mathcal{F}(\pi)={Q:\pi\text{ is a linear extension of }Q}. $$

The paper proves that this ambiguity can be quadratic in information:

$$ 2^{\lfloor n^2/4\rfloor} \leq |\mathcal F(\pi)| \leq 2^{\binom n2}. $$

Consequently, a single order-only trace cannot estimate ideal parallelism within a worst-case multiplicative factor smaller than $\sqrt n$.

Now suppose we observe independent, uniformly sampled traces $\pi_1,\pi_2,\ldots$. Their agreement order is

$$ R_k=\bigcap_{i=1}^{k}<_{\pi_i}. $$

Every true dependency remains in $R_k$. A comparison introduced only by serialization disappears once the two tasks are observed in the opposite order. The recovery time is therefore

$$ T(P)=\min{k\geq 1:R_k=\prec_P}. $$

Pathwise, recovery obeys the dimension floor

$$ T(P)\geq \dim(P). $$

For an incomparable pair ${x,y}$, let $a_{xy}=\Pr(x&lt;_{\pi}y)$ under a uniform random linear extension. The recovery tail satisfies

$$ \max_{{x,y}\in\mathcal I(P)} \left(a_{xy}^{k}+(1-a_{xy})^{k}\right) \leq \Pr(T(P)>k) \leq \sum_{{x,y}\in\mathcal I(P)} \left(a_{xy}^{k}+(1-a_{xy})^{k}\right). $$

This makes the main mechanism precise: recovery is slow when an independent pair can appear in either order, but one of those orientations is very rare.

Empirical study

The experiment uses random height-two posets and samples their linear extensions exactly uniformly. It then intersects traces until the agreement order equals the known ground truth.

The combined production artifact, combined-20260726-v2, contains:

• 13,800 independent poset instances;
• sizes $n\in{8,10,12,14,16,18,20}$;
• relation densities $p\in{0.10,0.25,0.50,0.75}$;
• a recovery cutoff of $k_{\max}=10{,}000$;
• zero censored observations;
• exact dimensions for all 4,000 instances at $n=8$; and
• 6,000 independently diagnosed instances with 2,000 post-recovery traces each for the rare-orientation analysis.

At $n=20$, mean recovery increased from $40.3$ traces at $p=0.10$ to $244.1$ traces at $p=0.75$. The longest observed recovery took $1,679$ traces.

The estimated median waiting scale of the hardest incomparable pair had Spearman rank correlation

$$ \rho=0.859 $$

with observed recovery time. In short: rare orientations explain most of the difference between easy and difficult instances.

What the implementation does

• Counts linear extensions with downset dynamic programming.
• Samples traces with exact integer conditional weights.
• Updates the agreement order using bitset intersection.
• Counts compatible transitive suborders exactly for $n\leq 8$.
• Uses the identity $|\mathcal F_k|=2^{|R_k|}$ whenever $R_k$ has height at most two.
• Computes exact small-instance poset dimension.
• Estimates rare incomparable-pair orientations using traces drawn independently after recovery.
• Derives model and trace seeds separately for deterministic reproduction.

Repository map

Path	Contents
dependency_geometry.tex	Paper source
dependency_geometry_revised.pdf	Revised ten-page paper
src/depgeom/	Sampler, counters, runner, aggregation, and plotting code
tests/	Exact-enumeration and invariant tests
artifacts/combined-20260726-v2/	Final combined tables, plots, events, and raw shards
aws/	Lambda handler, policies, payloads, and execution notes
figures/	Publication figures used by the paper and project site
index.html	GitHub Pages landing site

Local validation

Install the package in editable mode and run the test suite:

python -m pip install -e .
python -m pytest -q
python -m depgeom.benchmark --instances 1 --k-max 10000

No sweep result is considered valid unless the complete test suite passes.

The bundled arbitrary-order model counter is used for all agreement orders through $n=8$. On the development machine, the identity relation took about 5 seconds at $n=9$ and 88 seconds at $n=10$. Larger agreement orders therefore use $|R_k|$ as an upper bound on $\log_2|\mathcal F_k|$ until they become height two. This is an empirical implementation boundary, not a mathematical one.

Regenerating the final artifacts

Raw inputs remain under their original run prefixes. The combined outputs are also mirrored at:

s3://dependency-geometry-222259001580-us-east-1/runs/combined-20260726-v2/

Regenerate the tables, diagnostics, and figures with:

$env:PYTHONPATH = "src"
python -m depgeom.aggregate `
  --raw-directory artifacts/combined-20260726-v2/raw `
  --output-directory artifacts/combined-20260726-v2
python -m depgeom.dimension_report `
  --instances artifacts/combined-20260726-v2/instances.csv `
  --output artifacts/combined-20260726-v2/dimensions.csv `
  --max-n 8 --workers 4
python -m depgeom.plot `
  --artifact-directory artifacts/combined-20260726-v2
python -m depgeom.paper_stats `
  --artifact-directory artifacts/combined-20260726-v2 `
  --output artifacts/combined-20260726-v2/paper_stats.json