Polyvariance¶
A static-analysis design that retains distinct abstract approximations for selected calling contexts or value origins instead of merging them into one state.
Core Idea¶
Polyvariance is a choice in static program analysis to keep more than one abstract approximation of a shared program function, point, or value origin when different uses carry meaningfully different information. A monovariant analysis may join all callers' abstract inputs into one state, then return a combined result to each caller. A polyvariant analysis uses a chosen distinction—such as a recent call site, a receiver object's origin, or an abstract argument value—to maintain separate approximations. The aim is not to execute the program repeatedly; it is to avoid introducing impossible combinations through premature abstract merging.[1][2]
The screened seed described only a function analyzed once per call site. That is a common instance, but too narrow as the identity. Original research describes polyvariance as the degree to which an analysis structurally differentiates approximations of program values, and explicitly treats call, object, and argument-sensitive policies as alternatives. In an abstract-machine formulation, the policy can be embodied in how abstract addresses are allocated. These are different ways to choose which distinctions to preserve, not independent definitions of polyvariance.[1]
The gain is conditional. More contexts can reduce spurious joins and false alarms, but they can also multiply abstract states, analysis time, and memory without helping a particular client question. The states must still soundly cover feasible executions. A report that simply deletes inconvenient flows may look more precise but is not a valid polyvariant static analysis.[1][2]
Structural Signature¶
Sig role-phrases: abstract program facts → distinction policy → context-indexed approximations → sound propagation/rejoining → precision versus resource budget.
- Abstract program facts: The analysis approximates possible runtime values, points-to targets, or control flows. This is constitutive; without an abstract interpretation or comparable static approximation, there is no program-analysis polyvariance.[1][2]
- Distinction policy: A key chooses which uses remain separate: recent calls, receiver allocation, abstract arguments, or other value origins. The exact key is a variant; having a policy that differentiates relevant cases is constitutive.[1][2]
- Indexed abstract approximations: Each selected key has its own state or abstract address. A context label attached to a single universally joined state does not buy polyvariance. The representations may be a map from contexts to states or an equivalent allocation scheme.[2][1]
- Sound propagation and rejoining: Facts flow through each context, and returns are associated with compatible callers; joins still happen where required by the sound abstraction. The point is to delay harmful merging, not to omit feasible behavior.[2]
- Precision and budget boundary: Contexts must be represented tractably. The displayed call-string framework uses a finite context set; longer strings or richer state keys can raise the cost. A particular policy is useful only if its distinctions improve the analysis's target question sufficiently.[2][1][3]
What It Is Not¶
Polyvariance is not merely a program with many dynamic calls. A context-insensitive analysis of that program still combines them in one abstract state. It is not automatically equivalent to cloning the source function in the deployed program: logical copies of its analysis state suffice, while the executable need not change.[2]
It is not the same as flow sensitivity. A flow-sensitive analysis distinguishes facts before and after a statement, yet may still merge all callers at the shared function entry. Conversely, a context-sensitive analysis can distinguish callers while making coarser choices along a straight-line body. Those dimensions can be combined but should not be conflated.[2]
Nor is a larger context bound necessarily a better analysis. A call-string policy that splits many equivalent calls may cost more without changing useful answers; a receiver-based policy can preserve a different correlation. The best policy depends on program structure and the query, as illustrated by original comparisons between object- and call-site-sensitive pointer analyses.[1][3]
Scope of Application¶
Polyvariance lives in static analysis of programs: control-flow analysis of higher-order functions, interprocedural data-flow analysis, points-to analysis, type inference, and related abstract interpretations. In each case, the analyst decides what abstract value or program point could be polluted by a merge, chooses a bounded distinction policy, and checks the resulting precision/cost balance.[1][2]
For call-sensitive sign analysis, the context can be the most recent call node or a call string of length at most k. For functional or parameter sensitivity, the key can reflect abstract entry-state values rather than syntactic call location. In object-oriented pointer analysis, receiver or allocation-related contexts discriminate possible targets. These are not interchangeable parameter labels; each assumes different correlations in the program's behavior.[2][1][3]
The screened seed's “once per call site” formulation is therefore an example, not the scope. A data-polyvariant analysis may also distinguish value origins. Conversely, an informal human practice of considering multiple contexts is outside this entry unless it actually constructs sound abstract approximations of program executions.[1]
Clarity¶
Polyvariance clarifies where a reported imprecision entered the analysis. Suppose a result is “unknown” even though two callers supply separately recognizable values. Was a value truly unknown at runtime, or did the analyzer join the callers at the function entry? The context-indexed representation makes that question answerable: inspect the key and the states kept under it.[2]
It also separates the number of observed uses from the number of abstract variants. A program may call one function at thousands of sites yet an analysis can deliberately merge many into a few contexts. Another analysis may distinguish several abstract argument states at one syntactic site. “Polyvariant” names a structural choice about approximations, not a fixed one-to-one count of source calls.[1][2]
Manages Complexity¶
A real program may have unbounded executions, recursion, and many call histories. The analyzer cannot keep a distinct complete execution for each case, so it selects a compact context abstraction. With one-call-site sensitivity, many histories collapse to the same recent call; with a longer call string, more are kept apart. The key compresses execution history while preserving distinctions judged useful for the question.[2]
This is also the cost of the abstraction. A richer key increases the number of context–state pairs to compute to a fixed point. The original abstract-allocation account treats many named sensitivity variants as different allocation policies, making their trade-offs comparable instead of treating every technique as unrelated. The compression is successful when it avoids expensive false joins; it fails when it proliferates states with no relevant precision gain.[1]
Abstract Reasoning¶
Start with a suspected false positive. Identify the abstract state that contains incompatible possibilities and trace where they first joined. Propose a key that separates the relevant histories—perhaps the two call sites or two receivers. Then ask whether the new states still cover every feasible behavior assigned to their keys. Only after checking that soundness condition should one compare the precision of the output and the extra analysis cost.[2][1]
The simple sign-analysis case makes the inference concrete. A function called with zero at one site and a positive number at another can have a joined input that yields a top/unknown sign at both returns. Indexing by the two call sites retains the zero and positive approximations, allowing the returns to be matched to their callers. This does not prove that every program benefits from call-site sensitivity; it shows exactly what false join the chosen policy prevents.[2]
Knowledge Transfer¶
Within static program analysis the same design question travels from sign analysis to control-flow and pointer analysis: which abstractly distinguishable contexts should be retained so that a client query is neither swamped by spurious combinations nor too expensive to compute? Call strings, functional-state keys, and receiver keys supply different answers to that shared question.[1][2][3]
Outside that domain, “keep contexts separate before aggregating” resembles the live primes Partition and Context, but it is an analogy unless there are abstract program states and a soundness obligation over executions. The domain accent—control flow, abstract addresses, joins, and fixed-point computation—is not optional cargo. Importing the word into social, legal, or statistical reasoning would need an independently argued broader abstraction, not an assertion that those domains literally practice program-analysis polyvariance.
Examples¶
Call-site-sensitive sign analysis. Møller shows one function receiving 0 at one call node and 87 at another. A one-call-site context map gives separate abstract states: the first holds zero signs, the second positive signs. Mapped back: abstract facts = sign-lattice elements; distinction policy = call node; indexed approximations = zero and positive states; sound propagation/rejoining = each result returns to its matching call; budget = a finite one-level context set. The program function itself need not be duplicated in the executable.[2]
Object-oriented pointer analysis. A pointer analysis can keep receiver-related abstract contexts apart so that one method's possible target sets do not all merge. Jeon and Oh compare object-sensitive and call-site-sensitive implementations on Java programs and show that strategy and tuning affect both precision and scalability. Mapped back: abstract facts = points-to sets; distinction policy = receiver/allocation or call-site abstraction; indexed approximations = separate method-context states; sound propagation/rejoining = each context still overapproximates its assigned calls; budget = number and shape of contexts processed. The example shows a polyvariant setting, not universal superiority of one key.[3][1]
Structural Tensions¶
Discrimination versus state-space size. More keys can stop incompatible facts from joining but create more fixed-point work. Diagnostic: Which additional distinction measurably changes the client query's answer?[1]
Syntactic history versus semantic state. Call strings are explicit and easy to bound; abstract-input keys can merge equivalent calls but require a meaningful state abstraction. Diagnostic: Does the key follow the correlation that caused the false positive?[2]
Specialization versus sound coverage. Separate approximations can be sharper, but no feasible execution may be dropped merely to make a result look precise. Diagnostic: At each split and join, which runtime cases does each abstract state cover?[2]
Reusable partition idea versus domain-specific analysis. The general desire to avoid harmful aggregation travels widely; this named technique additionally needs program semantics, abstract values, and analysis budgets. Diagnostic: Is the receiving case a static program analysis or only an analogy about context?[1]
Structural–Framed Character¶
On the structural–framed spectrum, polyvariance is structural within static program analysis: call-site, receiver, argument and abstract-allocation policies all retain multiple approximations under a key. The defining test is whether a single approximation has been replaced by sound, context-indexed ones, not whether a practitioner prefers a certain tool. The key and budget vary, but the separative operation remains recognizable.[1][2]
Its evaluative weight is modest but not absent. “Polyvariant” describes an analysis structure; it does not by itself praise the analysis as accurate or economical. A designer may choose polyvariance because a client query suffers from false joins, yet more contexts can worsen resource use without a useful answer change. Precision and performance are outcomes to measure, not definitional virtues automatically conferred by the label.[1][3]
Its human-practice dependence lies in the choice of context abstraction and acceptable cost, not in the existence of the mathematical relation between keys and abstract states. Engineers decide whether the analysis needs one-call-site keys, receiver keys, or value-based keys. Once selected, the program and abstract transfer rules determine which states are computed; social consensus alone cannot turn an unsound dropped flow into a valid approximation.[1][2]
Its institutional origin is research in program analysis rather than a legal or administrative designation. Named approaches were proposed by researchers, but the identity is testable by inspecting the analyzer's representation and propagation. No standards body, profession's licensing decision, or organizational policy is required to make a given static analysis polyvariant.[1]
Its vocabulary travels among programming-language theory, compiler analyses and software-verification work because those settings share abstract program states. It does not travel intact to statistical subgrouping or legal contextual interpretation: there, “context” and “precision” lack the same soundness-over-executions meaning. Using “polyvariance” for those practices would import an analogy, whereas recognizing it in a new pointer analyzer identifies the same formal operation. A future broader prime might capture the portable anti-aggregation skeleton, but that would be a new identity rather than evidence that the exact named entry is already universal. Its character: structurally precise inside its home domain, framed by query- and budget-dependent design choices, and not independently established as a cross-domain prime.[1][2]
Structural Core vs. Domain Accent¶
The portable skeleton is preserve separately indexed interpretations where early aggregation would erase a decision-relevant distinction. The live Partition prime partially captures separation, while Context explains why a state needs a qualifying key. Neither supplies the full program-analysis identity: polyvariant approximations may overlap in the behaviors they cover, so a simple set partition is not an automatic strict parent; a contextual description is not necessarily an abstract interpreter. A more exact cross-domain skeleton, if wanted, is a future-prime question requiring independent evidence rather than a parent edge asserted here.[1][2]
The domain accent supplies what that skeleton leaves out. Abstract values stand for sets of possible program values; call graphs and returns determine propagation; the context allocator decides which histories or origins share an abstract address; joins must preserve a sound overapproximation; and fixed-point computation consumes time and memory. Those are not incidental examples. Remove them and the term no longer identifies the static-analysis technique described in the original research.[1][2]
Why not prime: The original evidence demonstrates variants across static program analyses, not three independent nonprogram domains with the same diagnostic test and intervention. A statistical subgroup analysis or legal context distinction may share an anti-aggregation intuition, but its objects, validity tests, and costs do not instantiate abstract addresses, sound program-state propagation and client-query precision literally. The broader skeleton may eventually be prime; the exact named polyvariance method remains a domain-specific realization. That is why this unparented draft does not connect to Partition or Context by a merely lexical edge.
Instantiates / Related Primes¶
No strict typed parent relation is asserted in the current DAG. Live Partition and Context are generic neighbors, but neither is an established necessary immediate genus of sound context-indexed program approximations; no strict edge was asserted from topical overlap. This placement awaits independent review.
Neighborhood in Abstraction Space¶
Polyvariance sits in a moderately populated region (58th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.
Family — Logical Inference, Modality & Conditional Structures (27 abstractions)
Nearest neighbors
- Profile-Guided Optimization — 0.85
- Program Transformation — 0.85
- 3SUM — 0.85
- Dynamic Problem — 0.85
- Array-access analysis — 0.84
Computed from structural-signature embeddings · 2026-10-08
Not to Be Confused With¶
- Monovariance: one merged approximation at the analysis target, regardless of how many calls exist.[2]
- Flow sensitivity: distinguishes program points over execution order; it does not by itself distinguish calling contexts.[2]
- Function inlining: physical or logical duplication can realize a kind of sensitivity, but polyvariance names the maintained abstract distinctions rather than source-code copying.[2]
- Universal precision gain: more contexts are not automatically better under a fixed budget or client query.[1][3]
References¶
[1] Thomas Gilray, Michael D. Adams and Matthew Might, “Allocation Characterizes Polyvariance: A Unified Methodology for Polyvariant Control-Flow Analysis,” ICFP (2016), 407–420, author-hosted abstract, doi:10.1145/2951913.2951936. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s ↩t ↩u ↩v ↩w ↩x ↩y ↩z
[2] Anders Møller, Static Program Analysis, interprocedural-analysis lecture, pp. 14–29, directly inspected; the lecture title page credits Møller alone. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s ↩t ↩u ↩v ↩w ↩x ↩y ↩z ↩27 ↩28
[3] Minseok Jeon and Hakjoo Oh, “Return of CFA: Call-site sensitivity can be superior to object sensitivity even for object-oriented programs,” Proceedings of the ACM on Programming Languages 6, POPL (2022), original abstract and publisher metadata, doi:10.1145/3498720. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g