TLDR: Researchers have introduced Doug, a typed computer language that uses differentiable vector-symbolic types to ensure all programs halt in polynomial time. Based on the Light Linear Functional Programming Language (LLFPL) and Vector-Symbolic Architectures (VSA), Doug’s types are learnable by neural networks. This approach aims to model human-like skill acquisition by drastically constraining the search space for program synthesis, offering a more efficient alternative to current brute-force AI methods.
A new computer language named Doug has been introduced, offering a novel approach to artificial intelligence by integrating learnable, differentiable types within a vector-symbolic architecture (VSA). This development aims to bridge the gap between current AI program synthesis methods and the efficiency of human skill acquisition, ensuring that all programs written in Doug are guaranteed to halt in polynomial time.
The Challenge of Skill Acquisition in AI
Traditional AI models, particularly in reinforcement learning, often focus on solving problems directly. However, a more profound view of intelligence, as proposed by Chollet (2019), suggests that an intelligent agent first acquires skills—procedures made of well-defined steps—and then uses these skills to achieve goals. This process, known as program synthesis, involves searching for a procedure with a desired effect. Unfortunately, synthesizing optimal programs is computationally very difficult, often requiring intractable, brute-force searches that are far slower than human learning.
Existing AI approaches, even advanced ones like DreamCoder and GPT o-series models, have been noted to behave similarly to exhaustive search, relying on increased computational power for performance gains. This contrasts sharply with human skill acquisition, which is significantly faster than brute-force methods, suggesting that humans employ powerful constraints to narrow down the search space for effective procedures.
Doug’s Innovative Approach
Doug addresses this challenge by constraining program synthesis to only consider programs that are likely to be useful and, crucially, that halt in polynomial time. This is achieved through a polynomial time type system, specifically an encoding of the Light Linear Functional Programming Language (LLFPL). A type system assigns types to program expressions, describing their data and operations, and a polynomial time type system specifically prohibits programs that would take an intractable amount of time to run.
The core innovation lies in making these types learnable by a neural network. Doug encodes types as points in a vector space using a Vector-Symbolic Architecture (VSA). In a VSA, structurally similar types are represented as spatially nearby vectors. This means that a neural network can learn to make good guesses about the structure of a skill program, significantly restricting the search space for program synthesis. The language builds on previous work by Tomkins-Flanagan and Kelly (2024), allowing neural networks to interpret points on an embedding space as systematically decodable types.
How Doug Works: A Blend of Architectures
Doug integrates several key components:
- Light Linear Functional Programming Language (LLFPL): This language forms the basis of Doug’s type system, known for its ability to express programs that halt in polynomial time. It achieves this by carefully managing resources and limiting recursion depth through mechanisms like ‘credit types’ and ‘boxed expressions’.
- Vector-Symbolic Architecture (VSA): VSAs provide the mathematical framework to encode arbitrary syntactic structures, including types, into high-dimensional vectors. This allows for operations like binding and composition, and critically, enables a measure of similarity between different vector representations.
- Holographic Declarative Memory (HDM): Based on Kelly et al. (2020), HDM provides a slot-value encoding scheme. This allows Doug to represent types in a way that structurally similar types, even with slight content variations, remain spatially close in the vector space, making them differentiable and learnable.
- Residue Numbers: Natural numbers within Doug are encoded using residue numbers, which leverage complex-domain holographic reduced representations to efficiently handle numerical operations within the VSA.
By combining these elements, Doug allows for the encoding of types, constants, and terms in a compositional manner, enabling neural networks to learn and manipulate these representations. The types in Doug are designed to be differentiable, meaning that a neural network can learn to refine its understanding of type structures through gradient descent, leading to smoother changes in type structure and content.
Also Read:
- ProofOptimizer: An AI System for Concise Formal Mathematics
- PolySkill: Empowering AI Agents with Adaptable Skills for the Open Web
Towards Human-Like Intelligence
The development of Doug represents a significant step towards modeling human mental representations and skill acquisition. Humans are adept at finding optimal representations and constraining their search for solutions, leading to efficient learning. Doug aims to replicate this by providing learnable, provably strong constraints that limit the complexity of program synthesis to tractable solutions.
While finding an optimal program remains computationally hard, Doug focuses on finding *any* program that satisfies a goal within a constrained, polynomial-time search space. This aligns with observations that human skill acquisition involves an easier search for correct behavior, even if the search for more efficient procedures remains challenging.
This research, detailed in the paper “Hey Pentti, We Did It Again!: Differentiable vector-symbolic types that prove polynomial termination”, offers a methodology for devising future type systems that can truly constrain program synthesis in a human-like manner, bringing AI closer to understanding and acquiring skills with human-level efficiency.
