arXiv:2610.09139v1 cs.AI

공간 복잡도 장벽 돌파 및 언어 모델 추론에의 응용

Breaking the Space Barrier and its Application to Language Model Inference

Arip Asadulaev

제출 2026-10-06

한국어 초록

언어 모델은 스키마를 따르는 JSON이나 타입이 지정된 인자를 갖는 도구 호출과 같이 구조화된 출력을 요구받는 경우가 점점 더 많아지고 있습니다. 오토마톤(automaton)이라는 작은 기계는 형식을 깨뜨리는 토큰을 금지함으로써 이러한 형식을 강제합니다. 본 연구에서는 이 기계에 드문 특성이 있음을 관찰했습니다. 즉, 기계의 임의의 상태에서 각 토큰은 정확히 하나의 경로로만 이어진다는 점입니다. 임의의 두 점을 연결하는 경로가 소수에 불과한 그래프는 복잡도 이론의 고전적인 연구 대상이며, 본 논문의 이론적 결과는 이러한 그래프에 관한 미해결 문제를 해결합니다. 즉, 매우 적은 메모리만으로도 해당 그래프가 실제로 소수의 경로를 갖는지 검증하면서 두 점이 연결되어 있는지 판별할 수 있습니다. 구체적으로 이 문제는 ReachUL, LOGDCFL, C=L, SC2 복잡도 클래스에 속하며, Savitch 정리의 고전적 O(log2 n)보다 낮은 O(log2 n/ log log n) 공간만을 필요로 합니다. 증명 이면의 구성 방식들은 추론 엔진으로 구현됩니다. 형식이 강제하는 텍스트는 모델 실행 없이 작성되고, 마스크는 테이블 없이 GPU에서 재계산되며, 재귀적 형식은 작은 스택을 사용하고, 모든 출력은 토큰 제한 내에서 유효성을 유지하며, 독립적인 필드들은 병렬로 디코딩된 후 검증됩니다. 16 GB Apple M2 Pro 환경에서 Qwen3.5-2B 및 4B를 사용해 해당 하드웨어의 표준 구성인 llguidance 기반 MLX와 비교한 결과, 스키마 제약 추출은 동일한 답변을 내면서도 1.2~1.3배 더 빠르게 완료되었고, 문법(grammar) 용량은 최대 1.5 GB 대신 3 MB에 불과했으며, 기존 테이블 방식에서는 메모리가 부족했던 환경에서도 단일 서버에 16개의 문법을 탑재할 수 있었고, 16개의 도구 호출 에이전트는 2.5배 더 빠르게 작업을 마쳤습니다.

원문 초록

Language models are more and more often asked for structured output: JSON that follows a schema, or a tool call with typed arguments. A small machine, an automaton, enforces the format by forbidding the tokens that would break it. We observe that this machine has a rare property: from any of its states, each token leads along exactly one path. Graphs in which only a few paths join any two points are a classical object of complexity theory, and our theoretical result settles an open question about them: one can decide whether such a graph connects two points while verifying that it really has few paths, with very little memory. Precisely, the problem lies in the classes ReachUL, LOGDCFL, C=L and SC2, and needs only O(log2 n/ log log n) space, below the classical O(log2 n) of Savitch's theorem. The constructions behind the proofs become an inference engine: text the format forces is written without running the model, the mask is recomputed on the GPU without any table, recursive formats use a small stack, every output stays valid under a token limit, and independent fields are decoded in parallel and verified. On one 16 GB Apple M2 Pro with Qwen3.5-2B and 4B, against MLX with llguidance, the standard setup for this hardware, schema-constrained extraction finishes 1.2- 1.3x sooner with the same answers, a grammar costs 3 MB instead of up to 1.5 GB, one server holds sixteen grammars where tables run out of memory, and sixteen tool-calling agents finish 2.5x sooner.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2610.09139v1

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.