PROBABILISTIC.lecture Probabilistic Source Code Modeling

To estimate the probability of an entire sentence, we use the joint probability P(A, B) = P(A) · P(B|A). For a sentence s = (w₁, w₂, …, wₙ), the chain rule expands this to P(w₁, …, wₙ) = ∏ⁱ P(wⁱ | w₁, …, wⁱ₋₁).

Walkthrough: “its water is so transparent”

Applying the chain rule step by step gives a product of P(its) × P(water | its) × P(is | its water) × P(so | its water is) × P(transparent | its water is so). The problem: finding exact long sequences in any corpus is extremely unlikely — even huge corpora will never contain most long word sequences.

When we estimate probabilities by counting, we are using Maximum Likelihood Estimation (MLE) — the simplest and most intuitive way to learn a language model. Count occurrences, divide by total observations, and that is your probability estimate.

P_MLE(w | context) = Count(context, w) / Count(context)

Worked Example

In a Java corpus, suppose Count(“(”, “for”) = 100 and Count(“(”) = 500. Then P_MLE(“for” | “(”) = 100 / 500 = 0.20.

To compute exact sequence probabilities, we would need enough data to observe every possible word combination. But the number of combinations is astronomical. With just 1,000 unique words, the number of possible 5-word combinations is C(1000, 5) = 8.25 × 10¹². No corpus is large enough to observe all of these.

The solution: instead of conditioning on the entire history, approximate by conditioning on only the last few words. This is the Markov assumption, and it gives us n-gram models.

The key idea: approximate the full conditional probability by looking at only the last N−1 tokens.

Start & End Tokens

Language models need to know where sequences begin and end. Special boundary tokens <s> and </s> make this possible. Without <s>, the model cannot learn which tokens start sequences. Without </s>, the model cannot learn when to stop generating.

Word frequencies in natural language (and code) follow a power-law distribution known as Zipf's Law: a small number of words occur very frequently, while a large number occur rarely. About 20% of words account for 80% of all occurrences. In code, tokens like ;, =, (, ), return, if dominate, while most custom identifiers fall in the long tail.

The Naturalness Hypothesis

Hindle et al. (ICSE 2012) showed that despite the theoretical expressiveness of programming languages, real programs are mostly simple and rather repetitive, with predictable statistical properties that can be captured in statistical language models — in many cases more so than English prose.

Training an n-gram model is simply counting. Split your corpus into training (80%) and test (20%) sets, count all bigram occurrences, then normalize each row to get probabilities.

In practice, a 3-way split is preferred: training (70%) for learning the counts, a held-out/validation set (10%) for tuning hyperparameters like interpolation weights λ, and a test set (20%) for final evaluation. To prevent data leakage, split by repository — all methods from one repo go into the same pool.

Extrinsic evaluation tests a model on a downstream task and measures accuracy. It is the gold standard but expensive and time-consuming. Intrinsic evaluation uses perplexity — a measure of model quality independent of any application. Lower perplexity = better model.

PP(W) = ( Πⁱ 1/P(wⁱ | wⁱ₋₁) )^(1/N)

If count(wⁱ₋₁, wⁱ) = 0, then P(wⁱ|wⁱ₋₁) = 0. A single zero probability makes the entire sequence probability zero and perplexity infinite.

Laplace (Add-1) Smoothing

P(wⁱ | wⁱ₋₁) = (count(wⁱ₋₁, wⁱ) + 1) / (count(wⁱ₋₁) + V)

where V = vocabulary size. Simple but crude — steals too much mass from observed events.

Instead of relying on a single n-gram order, blend multiple models together for more robust probability estimates. Linear interpolation blends P_uni, P_bi, and P_tri with weights λ₁ + λ₂ + λ₃ = 1. Stupid backoff tries the n-gram first; if count is zero, backs off to (n−1)-gram with penalty λ = 0.4.

Always picking the most likely next token (greedy decoding) produces repetitive, boring output. Sampling introduces variety by choosing randomly according to the probability distribution. Temperature (T) controls the sharpness of the distribution.

• T = 0 (greedy) — always pick the highest-probability token
• T = 1 — sample from the actual learned distribution
• T > 1 — flatten the distribution (more random/creative)
• T < 1 — sharpen the distribution (more focused/deterministic)

New code uses identifiers not in training data: myCustomHandler, calcNetRevenue. These have zero probability. Solution: replace rare tokens (count < threshold) with a special <UNK> token before training. The model learns “rare token behavior” — what typically follows or precedes an uncommon identifier. Modern solution: this is why modern LLMs use BPE (Byte Pair Encoding) instead of word-level tokenization. BPE breaks words into subword units, so even unseen identifiers can be represented as sequences of known subwords.

N-gram models have two fundamental limitations that neural language models overcome: parameter explosion (the number of parameters grows exponentially with the n-gram order) and no generalization (n-gram models cannot transfer knowledge between similar contexts).