Teaching a Code Model to Propose Numerically Exact Predicates for Hyperproperty Games

Many security and correctness requirements compare two runs of a program rather than one. Non-interference, for example, says that for every run there must exist another run with a different secret but the same public behaviour. Such requirements are called hyperproperties. Verifying them is hard because of the "for every run, there exists a run" structure. The approach that scales best is to turn verification into a game. An adversary picks one run step by step, and a verifier tries to build the matching run in response. If the verifier has a winning strategy, that strategy is a proof. For programs over integers, the game is played on an abstraction defined by predicates, such as "the secret in copy 1 minus the secret in copy 2 equals 3". Choosing these predicates is currently done by hand, and it is the main open bottleneck.

We propose to have a small, domain-pretrained language model propose those predicates while a symbolic game solver checks them. Soundness then never depends on the network. Predicates in these games are mostly linear relations between two program copies, and their constants are often not written anywhere in the source code. We therefore expect success to hinge on how the model represents numbers. Standard subword tokenizers split numbers into arbitrary chunks. The HPC code model MonoCoder erases numbers during pretraining entirely. We argue both are the wrong choice for this job. The proposal is a controlled test of whether keeping numbers value-aware during domain pretraining makes a model a better predicate proposer for hyperproperty games.

Core Claim

Game-based verification of infinite-state programs is sound and fast once the right predicates are given. Predicate abstraction for hyperliveness verification formulates the verification as a safety game over an abstract state space and solves it lazily with Z3 in the tool HyPA. On NonDetAdd, the lazy solver finishes in 4.5 seconds, while a direct solver times out after 300 seconds. However, the predicates must be supplied manually, and the authors leave automatic discovery as an open problem.

Our claim has two parts. First, a language model that proposes predicate sets can close this gap without weakening any guarantee. HyPA checks every proposal, and the model receives feedback from the solver when a proposal fails. Second, such a proposer works substantially better, especially when constants fall outside the training range, when its pretraining keeps numbers as value-carrying objects. We compare this against three alternatives: splitting numbers into subword chunks, splitting them into single digits, or anonymizing them as MonoCoder's Local Semantics Elimination does.

This inverts a design choice from domain-specific code pretraining. MonoCoder pretrains a 0.9B model on C/C++ HPC code. It replaces variable names, strings, and numbers with generic placeholders so the model learns structure rather than surface tokens. For completion measured by CodeBLEU, that helps. For verification, the numbers are the semantics.

The setup has the shape of a neural interactive proof, but with an important difference. Neural Interactive Proofs frames verification as a Stackelberg game between a weak trusted neural verifier and a strong untrusted prover. On code validation, its protocols improve verifier accuracy by approximately 11% over a solo verifier. Its certificates are, however, unreadable token exchanges, and its prover and verifier are general BPE-tokenized models. In our setting, the untrusted prover is the language model and the trusted verifier is a symbolic game solver. A "yes" answer is therefore a checkable winning strategy, not a learned judgment.

Research Program

The system is a propose-and-check loop around HyPA. The loop has three parts.

The input is a program together with a $\forall^k \exists^l$ specification in HyPA's observation-based HyperLTL. The model receives the program text, the specification, and the history of failed attempts. It outputs a candidate predicate set over the program copies, for example relations of the form $a \cdot x_1 + b \cdot x_2 \le c$ or parity constraints. It may optionally output hints about how to schedule the relative progress of the two copies.

HyPA then builds the abstract game lazily and tries to solve it. If the verifier wins, we are done and the certificate is sound. If it loses, we extract the abstract play in which the adversary wins. We concretize it with Z3 to check whether it is spurious, that is, a play the abstraction allows but no real pair of runs exhibits. A serialized version of this spurious play is fed back to the model as context for its next proposal. This is essentially the counterexample-guided refinement that the HyPA authors leave open, with the language model supplying the refinement step.

The supervision data comes from a program generator. It produces pairs of programs and specifications covering generalized non-interference, refinement, and symmetry. The programs contain loops, nondeterministic choices, and integer arithmetic with controllable constants and strides, in the style of NonDetAdd and the refinement examples in the HyPA suite. For each generated instance, we run an expensive offline enumeration over a linear-relation template space until HyPA certifies the instance. We keep the minimal certifying predicate set as the target. Instances where enumeration fails within a large budget are kept as unlabeled test cases.

We deliberately choose constants so that many needed predicate constants are derived rather than copied. For example, a relational offset may equal a loop bound times a stride minus one, which never appears in the text.

The main experimental axis is the model's number representation, holding all else fixed. We pretrain decoder models of roughly 150M parameters from scratch on the same token budget: a C subset of HPCORPUS (the MonoCoder corpus) with numbers kept, mixed with the generated verification programs. We compare four versions:

  • standard subword tokenization;
  • single-digit tokenization, following the digit-chunking study in Are Non-BPE Tokenizers Ready to Improve LLM Numeracy?;
  • Fourier number embeddings as in FoNE, where each number becomes one token with sine/cosine features at periods $10, 100, 1000, \dots$;
  • MonoCoder-style anonymization of numeric literals.

All four are then fine-tuned identically on the predicate data. We choose FoNE as the primary value-aware encoding because predicates here are dominated by addition, subtraction, and comparison. FoNE reports 100% accuracy on these operations with a 38M model and 64x less training data than subword or digit baselines on 6-digit addition. The "multiplication wall" that Efficient numeracy in language models through single-token number embeddings (Efficient Numeracy in Language Models through Single-Token Number Encodings) proves for sinusoidal embeddings matters little for linear predicates. That paper's BitTokens are an optional fifth arm if a program family needs products.

Pretraining on code rather than web text also addresses a question left open by FoNE and BitTokens. Both validated language ability only on FineWeb 10B. Huang et al. found that no numeracy-aware tokenizer beats BPE on both arithmetic and general language tasks at once. We measure held-out code perplexity for every arm to see whether that trade-off persists in a technical domain.

Baselines

The naive reference point is HyPA with no learned guidance. Its predicates come from syntactic harvesting: every comparison and guard in the program text, lifted to both copies, plus pairwise differences of same-named variables across copies. This is what a careful engineer would try first. It is run with the same solver and the same wall-clock and solver-call budgets as the learned proposers. Beating it means certifying strictly more instances within the budget, especially those whose needed constants are derived rather than literal. The file gives no reported predicate-discovery success rate for HyPA. The only reported HyPA figures are the 4.5-second lazy and 300-second timeout results on NonDetAdd, which we reproduce as a sanity check.

The strongest non-learned competitor is template enumeration with counterexample feedback. It enumerates linear relations over pairs of copy variables, drawing constants from a small set closed under sums and products of program literals. It refines by adding the predicates that separate the spurious play returned by Z3. We build it ourselves because no automated refinement for HyPA exists in the file. It gets the same solver-call budget as the model. The learned system beats it only if it reaches certificates in fewer solver calls on the same instances and certifies instances the enumeration cannot reach within budget.

The strongest learned competitor is a general, subword-tokenized model used as a prover, in the spirit of the GPT-4o provers in Neural Interactive Proofs. It is prompted with the same program, specification, and counterexample history, and receives the same number of proposal rounds. A second learned competitor is MonoCoder itself, fine-tuned on our predicate data. This tests directly whether a larger, anonymization-pretrained HPC model is handicapped. There is no reported result found on Lacuna for any language model proposing predicates or prophecies for hyperproperty games. The nearest reported figure is the approximately 11% verifier accuracy gain of nip/mnip on code validation, which is a different task.

The ablation that isolates the key ingredient is the four-way number-representation comparison at matched parameters, data, token budget, and fine-tuning recipe. A separate ablation removes counterexample feedback, so the model proposes once. This separates the value of refinement from the value of the initial guess.

Why not just…?

Why not just use classical counterexample-guided refinement with templates and skip the language model? This is the real threat. On small benchmarks like NonDetAdd, template enumeration may well match anything learned. It is therefore our strongest baseline, not a straw man. Our bet is narrower. Enumeration cost grows with the number of candidate constants and variable pairs, while a model that has learned how loop bounds and strides turn into relational offsets can jump to the right constant. The test is the scaled generator families, where we vary program size and constant magnitude and plot solver calls to certificate for both methods. If enumeration keeps pace, the honest conclusion is that learning adds nothing here, and we will report it.

Why not just prompt a frontier general model with tool access? The solver is already the tool, and every system gets it. What differs is the quality of the proposals. Are Non-BPE Tokenizers Ready to Improve LLM Numeracy? reports that GPT-4o reaches only 5% accuracy on long-digit integer addition. Efficient numeracy in language models through single-token number embeddings (Efficient Numeracy in Language Models through Single-Token Number Encodings) reports a chain-of-thought "reasoning tax" of 5,000 to 30,000 tokens on multi-digit math. Both suggest that derived constants will be a weak point for a general model. The general-model baseline measures this directly on our instances, rather than assuming it.

Why not just use single-digit tokenization, which needs no new embeddings? It is cheap and fixes much of the misalignment between digits. Distilling OLMo-3-7B down to single-digit chunks raised Tier 1 arithmetic accuracy from 27% to 83%. The cost is 1.9 to 2.6 times longer outputs, and verification contexts carry long counterexample histories. The digit arm is in the main comparison. If it matches FoNE on certification rate, the practical recommendation becomes "use digits and accept longer contexts."

Why not just fine-tune an existing subword code model rather than pretrain? Pretraining from scratch is expensive, and fine-tuning may suffice. The fine-tuned MonoCoder baseline, and a subword-tokenized arm fine-tuned identically, answer this. If they match the value-aware model on in-range constants but fall behind on out-of-range constants, pretraining with value-aware numbers is justified. If they match everywhere, it is not.

Proposed Experiments

The first check is the HyPA benchmark suite of $\forall^k \exists^l$ programs, including NonDetAdd and the refinement and non-interference examples. It is run under a fixed per-instance budget. We report the fraction certified, solver calls to certificate, and wall-clock time for every system. Soundness is not a metric, because every reported success is a strategy that HyPA checked.

The second and decisive check is extrapolation in magnitude. Models train on generated instances with constants below 100 and are tested on structurally identical instances with constants up to $10^4$ and with derived offsets. This probes the extrapolation gap that Do NLP Models Know Numbers? documented for fragmented number tokens. Our hypothesis is supported if FoNE's certification rate degrades markedly less than the subword and digit arms, with the anonymization arm worst. It is refuted if the four arms are indistinguishable, or if the ordering follows only perplexity.

The third check asks whether the proposer transfers beyond its training distribution. We use finite-state benchmarks from the HyPro suite, which verifies instances of up to 55,000 states using prophecy variables, and the software-doping emission models from Verifying Hyperliveness, which reports 1.8 to 160 seconds per instance. On these, the model proposes predicates or prophecy hints and the existing tools check them. We report any change in time relative to the published figures. The measure of success is fewer solver calls to reach the same verdict.

Finally, held-out code perplexity for each arm tells us whether value-aware numbers cost anything on technical text. This extends the arithmetic-versus-language trade-off question from web text to a verification domain.