Getting Python Types Right with RightTyper

This paper introduces RightTyper, a novel hybrid tool that combines execution-based observations with static analysis and adaptive sampling to generate accurate Python type annotations with significantly lower runtime overhead and higher precision than existing static, dynamic, or AI-based approaches.

The Gist

Imagine you are the editor of a massive, chaotic library. The books (your Python code) are written in a language that is incredibly flexible and fun to write, but it lacks a strict cataloging system. In this library, a book titled "Data" could contain a recipe, a phone number, or a map, and the librarian (the computer) doesn't know which until you actually open the book and read it.

This flexibility is great for writing, but it's a nightmare for finding things later. If you want to build a better catalog (add type annotations so other tools can help you), you have to manually read every single book and write down exactly what's inside. That takes forever and is boring.

Enter RightTyper, a new, super-smart librarian assistant that solves this problem.

The Problem with Old Assistants

Before RightTyper, there were three ways to try to catalog these books, and they all had flaws:

1. The "Guess-Who" Assistant (Static Analysis): This assistant never opens the books. It just looks at the cover and the table of contents. It tries to guess what's inside based on the title.
   • The Flaw: Because Python is so flexible, the cover often lies. The assistant gets scared and says, "This book might contain a recipe, a phone number, or a map," so it writes a very vague label. It's safe, but not very helpful.
2. The "AI Oracle" (AI-Based Methods): This assistant has read millions of books and uses a neural network to guess what's inside.
   • The Flaw: It's a good guesser, but it's not a truth-teller. It might confidently say, "This is definitely a recipe," when it's actually a map. It's fast, but it can be wrong, and in a library, wrong labels cause chaos.
3. The "Over-zealous Scribe" (Dynamic Tools like MonkeyType): This assistant actually opens every single book, reads every word, and writes down exactly what it sees.
   • The Flaw: It's incredibly accurate, but it's also exhausting. It slows the library down to a crawl (sometimes making it 270 times slower!) because it's constantly flipping pages. It also writes down everything, even the weird, one-off things that happened by accident, leading to messy, confusing labels.

The RightTyper Solution: The "Poisson Detective"

RightTyper is a hybrid. It doesn't guess, and it doesn't obsessively read every page. Instead, it uses a clever strategy called Adaptive Sampling.

Think of RightTyper as a detective who uses a randomized camera.

• The Camera Trick (Poisson Sampling): Instead of watching the library 24/7 (which slows everything down), RightTyper sets up a camera that snaps a photo at random intervals.

  • When the camera is off, the library runs at normal speed.
  • When the camera flashes (a "capture window"), it snaps a picture of what's happening.
  • Because the timing is random and mathematically perfect, it captures a fair, representative sample of the library's activity without slowing it down. It's like taking a few high-quality snapshots of a busy party rather than filming the whole thing for 10 hours.

• The "Good-Turing" Magic for Big Boxes: Sometimes, the library has huge boxes (containers like lists or dictionaries) with thousands of items inside.

  • Old assistants would dump the whole box out to count everything.
  • RightTyper uses a math trick called Good-Turing Estimation (invented by Alan Turing during WWII!). It takes a small handful of items, looks at how many new types it finds, and calculates: "Okay, I've seen enough. I'm 99% sure I know what's in this box." It stops early, saving massive amounts of time.

• The "Context" Detective: RightTyper doesn't just look at the snapshot; it also looks at the book's cover (Static Analysis) to understand the structure. It combines the "what I saw" (Dynamic) with "what the structure suggests" (Static) to write the perfect label.

Why It's a Game Changer

RightTyper is like a librarian who is:

1. Fast: It only slows down the library by about 27% (compared to the 27,000% slowdown of the old scribes).
2. Accurate: It produces labels that are 99% similar to what a human expert would write.
3. Smart: It understands that if a function adds two numbers, it should be labeled "Number," but if it adds two strings, it should be "Text." It doesn't just say "It could be anything." It figures out the pattern.

The Bottom Line

Writing type annotations for Python code used to be like manually cataloging a million books by hand. RightTyper is a tool that uses smart, random sampling and math tricks to do the job for you. It's fast enough to run while you work, accurate enough to trust, and smart enough to catch the patterns that humans might miss. It turns a chaotic, untyped library into a well-organized, searchable system with almost no effort from you.

Technical Summary

Here is a detailed technical summary of the paper "Getting Python Types Right with RightTyper".

1. Problem Statement

Python is a dominant programming language, yet the vast majority of its codebases remain untyped. While static type checkers (e.g., mypy, pyright) offer significant benefits in bug detection, code readability, and IDE support, manual annotation is tedious and time-consuming. Existing automatic type inference tools fall short in three critical areas:

• Static Approaches: Struggle with Python's dynamic features (e.g., runtime type changes, reflection), often inferring overly broad or conservative types that reduce the utility of type checkers.
• AI-Based Approaches: Use machine learning to predict types but are inherently unsound; predictions may not reflect actual program behavior, leading to false positives/negatives. They also struggle with rare or user-defined types.
• Dynamic Approaches (e.g., MonkeyType, PyAnnotate): Observe actual runtime behavior, yielding precise types. However, they suffer from extreme runtime overhead (up to 270× slowdown), lack support for inferring variable types, and often produce annotations that cause runtime errors due to reliance on raw runtime type names.

2. Methodology: RightTyper

RightTyper is a novel hybrid approach that grounds type inference in actual program execution while minimizing overhead through principled sampling and combining runtime data with static analysis.

A. Adaptive Sampling via Poisson Process

To address the overhead issue, RightTyper does not instrument every function call. Instead, it uses a Poisson process to create brief, randomly timed "capture windows."

• Warmup Phase: The first $k$ invocations (default 5) of every function are captured unconditionally to ensure basic coverage.
• Poisson Sampling: After warmup, monitoring is enabled only during exponentially distributed time intervals. Most function calls execute without instrumentation, drastically reducing overhead.
• Container Sampling: For container types (lists, dicts), RightTyper fully scans small containers but uses Good–Turing estimation for large ones. This statistical estimator determines when to stop sampling based on the proportion of "singleton" types (types seen only once), ensuring representative coverage without exhaustive scanning.

B. Hybrid Inference Pipeline

RightTyper combines three data sources to generate high-quality annotations:

1. Runtime Observations: Captures types of arguments, return values, and variables at function exit. It tracks container contents and handles iterators by inspecting underlying iterables.
2. Static Analysis & Name Resolution: Uses static analysis to identify variable scopes and resolve import paths. It constructs a mapping from type objects to canonical import paths (handling C-implemented types) and uses typeshed stubs for standard library types.
3. Pattern Recognition & Generalization:
   • Type Patterns: Instead of naively creating unions (e.g., float | str), RightTyper analyzes call traces to detect recurring patterns. It generalizes these into type variables (e.g., T) or generic parameters (e.g., list[T] -> T).
   • Inheritance Handling: Correctly handles self types in methods (using Self or the defining class) and respects the Liskov Substitution Principle by merging observed types with inherited types in overridden methods.
   • Array Shapes: For numerical arrays (e.g., NumPy), it infers and annotates shape dimensions (e.g., Float64[ndarray, "10 20"]).

C. Annotation Generation

The system simplifies inferred types to improve readability (e.g., merging int and float into float based on Python's numeric tower) and guards new imports with TYPE_CHECKING to prevent runtime circular dependency errors.

3. Key Contributions

1. RightTyper System: A novel hybrid type inference tool that balances runtime fidelity with low overhead.
2. Open-Source Prototype: A fully functional implementation (~8,000 lines of Python) available on GitHub.
3. Enhanced TypeSim Metric: An improved implementation of the TypeSim semantic similarity metric, addressing limitations in the original (e.g., handling inheritance, protocols, and complex generics) to better evaluate type quality.
4. Comprehensive Evaluation: Extensive empirical evaluation against static, AI-based, and dynamic baselines on both synthetic benchmarks and real-world code.

4. Results

The evaluation was conducted on TypeEvalPy (a synthetic benchmark) and real-world packages (black, flask, httpx, pylint, rich).

• Accuracy (TypeSim Score):

  • TypeEvalPy: RightTyper achieved 99.8% similarity to ground truth, outperforming GPT-4o (95%) and static tools like pytype (60.6%).
  • Real-World Code: RightTyper achieved 77.2% similarity to developer-written annotations, significantly beating GPT-4o (72.6%) and MonkeyType (57.5%).
  • Key Differentiator: RightTyper is the only tool that successfully infers variable types and handles complex generic patterns, whereas MonkeyType and QuAC failed to infer variable types entirely.

• Runtime Overhead:

  • RightTyper incurs only ~27% runtime overhead (geometric mean 1.27× slowdown).
  • This is a massive improvement over existing dynamic tools: ~19× faster than MonkeyType (which had a 24.71× slowdown) and significantly faster than PyAnnotate.
  • On real-world code, RightTyper completed in 8 minutes, compared to MonkeyType's 4 hours and 44 minutes.

• Sampling Efficiency:

  • RightTyper's Poisson sampling covered 68% more functions than MonkeyType's Bernoulli sampling (at $p=0.01$) while recording 6.7× fewer traces.
  • Container sampling using Good–Turing estimation achieved 99.6% perfect recall while reducing element inspections by 93.3% compared to exhaustive scanning.

5. Significance

RightTyper represents a breakthrough in making static typing practical for Python.

• Practicality: By reducing runtime overhead to a manageable ~27%, it enables developers to run type inference on production code or large test suites without prohibitive performance penalties.
• Quality: It produces annotations that are semantically closer to human-written code than any previous method, including advanced LLMs. Its ability to generalize types (using type variables) rather than just listing unions makes the resulting code more robust and readable.
• Completeness: It addresses critical gaps in previous tools, such as inferring variable types, handling inheritance correctly, and supporting array shape annotations, making it a comprehensive solution for modern Python codebases.

In conclusion, RightTyper successfully bridges the gap between the precision of dynamic analysis and the efficiency required for real-world adoption, offering a viable path to automatically type-annotate the vast majority of untyped Python code.