PaperlayerView exact revision on arXiv

Source-linked AI summary

Statically Contextualizing Large Language Models with Typed Holes

Andrew Blinn, Xiang Li, June Hyung Kim, Cyrus Omar

arXiv:2409.00921v1cs.PLcs.AIcs.SE

TL;DR

LLM code completion lacks reliable evidence when task-relevant definitions are outside the cursor window or absent from training data. The paper combines typed-hole information, language-server retrieval, and iterative error correction, finding strong gains from type information while evaluating an idealized and limited scope.

  • Problem

    LLM code completion lacks reliable evidence when task-relevant definitions are outside the cursor window or absent from training data.

  • Method

    The paper combines typed-hole information, language-server retrieval of related definitions, and iterative syntax/type-error correction for LLM hole filling.

  • Results

    Type information drastically improves StarCoder2-15B correctness by an order of magnitude, while adding headers yields a further 50% relative-performance increase.

  • Takeaways & Limitations

    Typed holes connect local programming intent with broader semantic context, and language-aware assistants may outperform language-agnostic vector retrieval.

  • Takeaways & Limitations

    The evaluation uses an idealized baseline with little relevant cursor-window code, and TypeScript MVUBench may not represent broader TypeScript programming styles.

Abstract

from arXiv · show

Large language models (LLMs) have reshaped the landscape of program synthesis. However, contemporary LLM-based code completion systems often hallucinate broken code because they lack appropriate context, particularly when working with definitions not in the training data nor near the cursor. This paper demonstrates that tight integration with the type and binding structure of a language, as exposed by its language server, can address this contextualization problem in a token-efficient manner. In short, we contend that AIs need IDEs, too! In particular, we integrate LLM code generation into the Hazel live program sketching environment. The Hazel Language Server identifies the type and typing context of the hole being filled, even in the presence of errors, ensuring that a meaningful program sketch is always available. This allows prompting with codebase-wide contextual information not lexically local to the cursor, nor necessarily in the same file, but that is likely to be semantically local to the developer's goal. Completions synthesized by the LLM are then iteratively refined via further dialog with the language server. To evaluate these techniques, we introduce MVUBench, a dataset of model-view-update (MVU) web applications. These applications serve as challenge problems due to their reliance on application-specific data structures. We find that contextualization with type definitions is particularly impactful. After introducing our ideas in the context of Hazel we duplicate our techniques and port MVUBench to TypeScript in order to validate the applicability of these methods to higher-resource languages. Finally, we outline ChatLSP, a conservative extension to the Language Server Protocol (LSP) that language servers can implement to expose capabilities that AI code completion systems of various designs can use to incorporate static context when generating prompts for an LLM.

1 Introduction

LLM code assistants often lack semantically relevant definitions outside the cursor window, causing incomplete or hallucinated code. The paper uses language-aware static context from language servers and evaluates it in Hazel and MVUBench.

  • Motivation: Cursor-window prompting misses task-relevant definitions located elsewhere, so LLMs may generate no completion or plausible-but-incorrect code.The problem is especially acute for MVU applications whose Model, Action, and related helpers may be defined across files.
  • Motivation: Existing retrieval methods use lexical or vector heuristics and can retrieve irrelevant same-named definitions while incurring token and generation costs.The paper motivates retrieval that prioritizes semantic relevance rather than exhaustive repository context.
  • Approach: The proposed language-aware approach uses a language server to identify a hole’s type and typing context, then transitively retrieves relevant type definitions and helper-function headers.For an update hole, the server can retrieve Model and Action definitions and related helpers up to a token limit.
  • Approach: Static error correction feeds syntax and type errors from generated completions back to an instruction-tuned model for iterative repair.This trades additional latency for potentially improved correctness over multiple correction rounds.
  • Scope and platform: The methods require a capable language server with robust syntax- and type-error recovery and are evaluated primarily in Hazel, a low-resource typed functional language.Hazel’s typed holes provide meaningful program sketches even when errors are present, while LLMs may otherwise borrow syntax from related languages.
  • Evaluation: The evaluation introduces MVUBench, a repository-level benchmark of high-context MVU web applications with application-specific datatypes and unit-test-based correctness evaluation.The benchmark targets limitations of existing datasets, including data contamination, language exclusivity, and reliance on brittle textual similarity.

2 Static Retrieval and Error Correction in the Hazel Assistant

The Hazel Assistant combines fast type-directed local completion with LLM-based hole filling informed by static context. Its language-server dialogue can iteratively correct syntax and type errors in generated code.

  • 2.1 Hazel: Hazel provides total syntax and type-error recovery through automatic hole insertion, keeping every editor state a semantically meaningful program sketch.This allows editor services such as completion to continue operating despite errors.
  • 2.1 Hazel: In the EmojiPaint example, the update function transforms a Model in response to an Action, while relevant types and helper functions reside in different files.This cross-file structure motivates exposing static information around the hole.
  • 2.2 Hazel Assistant: The Hazel Assistant offers fast local completions through type-directed lookahead using localized syntactic and static information.It can operate even with syntax errors because Hazel tracks outstanding syntactic obligations.
  • 2.2 Hazel Assistant: The developer requests an LLM completion by inserting ?? into an expression hole, after which GPT-4 generates a more substantial completion that can be inspected for type errors.The generated completion is presented as an alternative to the assistant’s smaller type-directed tokens.
  • 2.3 Generative hole filling: The generative process forms a trialogue: Hazel supplies a program sketch augmented with static retrieval, the model proposes a filling, and subsequent error messages prompt correction.Error-correction rounds are capped at two to limit latency.

2.4 System Message: The Hazel Crash Course

Hazel contextualizes hole filling by combining expected-type information, recursively retrieved definitions, and relevant headers into an LLM prompt. This language-aware retrieval respects necessary type relevance and lexical scope, unlike imprecise token-based retrieval.

  • System message: The system message instructs the LLM to replace a hole sentinel with a code fragment and return only code.It also includes Hazel-specific syntax guidance and few-shot sketch-completion examples.
  • Type retrieval: Type retrieval recursively collects definitions of aliases occurring in the hole’s expected type until reaching base types.For the EmojiPainter example, retrieval expands Model and Action into Grid, Emoji, Row, and Col definitions.
  • Type retrieval: The language server extracts the hole’s expected type even at positions where bidirectional typing provides type constraints.For the update sketch, the expected type is (Model, Action) -> Model.
  • Relevant type definitions: Without static context, the model may hallucinate incorrect constructors and unsupported Hazel syntax despite recognizing the general MVU task.Figure 7 illustrates hallucinated Action constructors and an invalid record-style Model definition.
  • Relevant type definitions: Static retrieval provides definitions that are necessarily relevant, supports recursive multi-hop lookup, and respects lexical scope.These guarantees distinguish semantic retrieval from vector retrieval based on approximate similarity.

2.6 Relevant Headers from the Typing Context

Header retrieval supplements type definitions with names and types of context values selected by their typed relationship to the expected result. The proof-of-concept ranks and truncates these entries while avoiding uninformative base-type confounders.

  • Relevant headers: Header retrieval adds names and types of relevant values, typically functions, analogous to a type-directed autocomplete menu.The method identifies target types, filters context entries by type relatedness, scores them, and returns a truncated prefix.
  • Identification of target types: Target-type extraction begins with the hole type and extends arrow types through their return types and product types through their components.The example expands (Model, Action) -> Model to include Model, Grid, Emoji, and [Emoji].
  • Identification of target types: The approach currently deconstructs compound types only shallowly, while deeper destructuring and input-type targets remain possible extensions.The authors describe the current strategy as sufficient for their immediate relevance-identification purpose.
  • Relevant headers: Unaliased base types such as Bool and String are excluded because standard-library functions on them are numerous and difficult to distinguish by type alone.The paper assumes these libraries are already familiar to the model from pretraining or fine-tuning.
  • Relevant headers: Context entries receive default scores, with incomplete types down-weighted according to their ratio of unknown to known type constructors.Entries with equal scores retain Hazel’s locality ordering.
  • Relevant headers: For the EmojiPainter example, retrieved headers include model_init, fillRowInGrid, clearGrid, and updateGrid with their associated types.These entries are formatted as code sketches for language-model ingestion.

2.7 Syntactic and Semantic Error Correction

After generation, Hazel parses and partially type-checks the completed sketch, serializes static errors, and feeds them back to the model for iterative repair. The correction loop is bounded by context length and typically benefits from only a few rounds.

  • Error correction: Generated code is substituted into the sketch, then Hazel reports syntax and type errors even when delimiters or other program elements are missing.The language server’s incremental parsing enables partial type-checking of incomplete programs.
  • Error correction: Static errors are appended to the original prompt so the LLM can generate successive corrections.The language server should expose localized error locations and messages, ideally reporting all errors rather than only the first.
  • Error correction: GPT-4’s 8k-token context limits the process to about five correction rounds, while two rounds often eliminate static errors and additional rounds show diminishing returns.The round limit arises because the error log grows with each iteration.

2.8 Experimental Evaluation

The evaluation uses five MVU applications and compares static retrieval, error correction, exhaustive retrieval, and vector retrieval under controlled completion trials. It frames context-free completion as a lower bound and exhaustive retrieval as a token-inefficient upper bound, while noting limitations of the vector baseline.

  • Benchmark and setup: The benchmark contains five MVU applications: Todo, Room Booking, Emoji Painter, Playlist Manager, and Password Strength Checker.Each application includes a simulated repository and a 10–15-test suite for expected MVU behavior.
  • Experimental design: The main experiment runs 320 completion trials across eight feature configurations, five sketches, and 20 trials per combination.The configurations ablate type retrieval, header retrieval, and up to two error-correction rounds.
  • Feature ablation experiment: The no-static-retrieval configurations serve as a lower-bound baseline because the model receives only a brief update-function comment.This baseline represents assistants that do not attempt repository-level retrieval.
  • Comparison baselines: Exhaustive retrieval of all application code up to the context limit serves as a token-inefficient upper bound on performance.The comparison tests whether targeted static context can approach broad retrieval without including everything.
  • Vector retrieval with confounds: The vector-retrieval baseline combines the five programs and Hazel’s standard library into a 1000-line corpus, then retrieves six 150-character chunks by cosine similarity.The chunk and retrieval sizes are calibrated to approximately match the average static-retrieval context length.
  • Vector retrieval with confounds: The vector baseline is intentionally structurally agnostic despite available chunking strategies that might improve retrieval quality.The paper notes that semantic and associative retrieval could ultimately be combined rather than treated as mutually exclusive.

2.9 Hazel GPT-4 Results

GPT-4 completions improved as static semantic context increased, with type definitions enabling scaffolding and headers and error rounds providing multiplicative gains. The evaluation also exposed confounds and practical costs in retrieval comparisons and guided completion latency.

  • The no-context baseline often produced syntactically incorrect code by hallucinating data types and unsupported OCaml-style record syntax.Figure 8 reports the GPT-4 guided-completion evaluation across 20 trials per configuration at temperature 0.6.
  • Type definitions were necessary for scaffolding the update function, while adding relevant headers increased test performance threefold when combined with types.Headers alone had little effect on correctness, but their combination with type definitions produced a large multiplicative improvement.
  • Error rounds increased performance fourfold with types without headers and 1.5-fold with both types and headers, especially converting almost-correct completions into correct ones.Error correction was ineffective when generated code largely hallucinated types and functions.
  • Poor error messages could still help correction because identifying that a syntax error existed sometimes gave the model enough additional context to fix it.Figure 11 shows a parse error corrected despite an unclear Hazel diagnostic.
  • The types-plus-headers configuration performed well against vector retrieval, but the comparison was disproportionately driven by one Todo-specific confounding chunk retrieved for every example.The chunk encouraged Todo or hybrid implementations because it coincidentally contained the words Model and Action.
  • Types-plus-headers results were similar to exhaustive retrieval, but the small programs and limited context-size differences prevented a significant distinction between them.Average retrieval contexts were 890 characters for types plus headers and 1370 for exhaustive retrieval, so more data is needed for a conclusive cost comparison.

2.10 Hazel StarCoder2-15B Results

For Hazel, StarCoder2-15B benefits substantially from static type and header retrieval, although irrelevant headers can hurt some sketches and vector retrieval performs worse.

  • Type information increases StarCoder2-15B’s correct solutions by an order of magnitude, while headers add a further 50% relative improvement.The comparison uses 20 trials per configuration at temperature 0.6.
  • Two sketches, BO and TO, degrade after header inclusion because the smaller model follows type-appropriate but irrelevant retrieved headers.The authors hypothesize that StarCoder2 is especially sensitive to information near the context window’s end.
  • Vector retrieval performs significantly worse than static retrieval for StarCoder2 in both absolute and relative terms.The authors conjecture that chunk-truncation syntax errors make the vector-retrieval prompt less effective.

3 Static Retrieval in TypeScript

The TypeScript experiments adapt static retrieval through language-server services and find results broadly similar to Hazel, with stronger baseline performance and weaker dependence on headers and error rounds.

  • 3.1 Methodology: The TypeScript experiments emulate typed holes with a generic function and use Hover plus Go to Type Definition to recursively retrieve relevant types.The emulation works consistently for function bodies but fails in some syntactic positions.
  • 3.1 Methodology: The TypeScript language server lacks direct access to typing contexts and in-scope variables, so relevant-header retrieval was simulated manually rather than implemented generally.The authors used this workaround instead of undertaking a compiler-level intervention.
  • 3.2 TypeScript GPT-4 Results: TypeScript static-retrieval results broadly resemble Hazel’s, but the higher-resource language achieves better overall completions and sometimes passes tests without type information.With type definitions included, the TypeScript results are flatter than Hazel’s.
  • 3.2 TypeScript GPT-4 Results: Headers improve test-pass ratios by 3× in Hazel and 1.5× in TypeScript, where models more often produce equivalent working logic inline without retrieved headers.This comparison indicates a smaller header effect in TypeScript than in Hazel.
  • 3.2 TypeScript GPT-4 Results: Error rounds matter less in TypeScript: the with-versus-without ratio is about 1.2, compared with about 2 in Hazel.The authors attribute this likely difference to greater familiarity with TypeScript syntax.
  • 3.2 TypeScript GPT-4 Results: Performance relative to exhaustive and vector-retrieval baselines is broadly in line with Hazel, including the latter’s high per-example variance.The TypeScript StarCoder2 results are also described as roughly matching Hazel modulo the preceding considerations.

4 Threats to Validity

The validity threats concern benchmark representativeness, idealized baselines, header availability, and whether the small translated TypeScript setting generalizes to broader programming practice.

  • Header improvements depend on many relevant functions already being implemented, and validating their commonness requires larger, more neutrally selected programs.This constrains how broadly the reported header effect should be generalized.
  • MVUBench is intentionally a challenge benchmark rather than a representative sample of all coding tasks.Its purpose is to evaluate semantic contextualization techniques.
  • The TypeScript benchmark closely translates Hazel code, leaving applicability to broader TypeScript programming styles unresolved.The MVU paradigm is used in TypeScript, but the broader scope remains an open question.
  • The baseline setup assumes little relevant code in the cursor window, so the large gains from adding context may not reflect typical real-world windows.The paper calls for validation of how frequently such sparse-context scenarios occur in practice.
  • The RAG baseline is simplistic, and the conjoined codebase used to build its embedding database may not represent a real large-scale codebase.More sophisticated retrieval methods could therefore provide a different comparison.

5 ChatLSP

ChatLSP is proposed as a conservative LSP extension exposing static-contextualization capabilities through language-server commands, while leaving implementation choices to each language server.

  • The interface is presentation-centric, using strings and affordances rather than language-specific semantic data types.This distinguishes the proposed ChatLSP layer from the internal Static Contextualization API.
  • ChatLSP exposes commands for tutorials, expected types, relevant types, relevant headers, and static-error reports to AI completion systems.These capabilities support prompt construction and error-correction interaction with language servers.
  • ChatLSP leaves command implementations to language servers, making adoption straightforward for languages with rich static analysis and existing hole-oriented support.The paper gives GHC with Haskell as an example.
  • The internal API computes expected types, typing contexts, aliases, target types, filtered contexts, header scores, and static errors from a program location.These operations provide the language-server-side machinery underlying ChatLSP.
  • Relevant types are retrieved recursively through aliases, while headers are filtered by relevant types, scored, sorted, and truncated to a fixed number.The pseudocode connects ChatLSP retrieval methods to the static-contextualization API.

6 Related work

Related work addresses semantic contextualization through retrieval, static analysis, learned selection, and error correction. This paper distinguishes its approach by using language-aware static information, while positioning several alternatives as complementary or promising directions.

  • Error correction: Error looping is widespread, but the paper argues that combining correction with contextualization is most effective in context-poor settings, particularly for Hazel.Error correction alone is not presented as the novel contribution.
  • Semantic contextualization: Language-aware static retrieval uses type and binding information rather than language-agnostic token heuristics to contextualize code generation.The paper relies on language-server services for semantic information and analyzes candidate completions through static methods.
  • Retrieval and analysis: Prior systems retrieve repository code using reinforcement learning, vector similarity, coarse static relationships, or program analyses for completion and repair tasks.These approaches differ in how they select context and how much semantic structure they expose.
  • Future directions: The paper identifies future combinations involving static retrieval with learned context selection, richer analyses, dynamic information, and library searches.These directions aim to improve context selection or extend the kinds of information available to completion systems.
  • Related contextualization methods: Several methods retrieve or learn from semantic context, including IDE-provided information, API documentation, issue-derived signatures, relevant types, and localized dynamic information.The paper describes these approaches as complementary, related, or alternative forms of contextualization.

7 Discussion and Conclusion

The discussion presents typed holes and language-server integration as a foundation for connecting local intent with broader semantic context. It reports advantages over vector retrieval, while noting portability challenges and opportunities for richer contextualization.

  • Foundations: Typed holes connect local expressions of intent to broader semantic context through typing contexts, grounding Hazel’s approach in gradual contextual type theory.Hazel provides total syntax and type-error recovery with holes, making it an environment for this form of contextualization.
  • Scope: The techniques can be ported to languages such as TypeScript, although standard language-server limitations make porting difficult.The paper presents TypeScript as evidence of applicability beyond Hazel, while retaining this implementation qualification.
  • Implications: The paper reports that language-aware assistants may significantly outperform language-agnostic retrieval systems over the short and medium term.This conclusion is based on comparisons with vector retrieval and is qualified as a possibility extending further into the future.
  • Future work: Future work could add dynamic test results, other static and dynamic analyses, and library searches for helpers that are not yet imported.These additions are presented as avenues for extending semantic contextualization.
Loading 2409.00921v1…